source: josm/trunk/src/org/openstreetmap/josm/data/osm/DataSetMerger.java@ 11357

Last change on this file since 11357 was 10308, checked in by Don-vip, 8 years ago

sonar - squid:S1854 - Dead stores should be removed
  • Property svn:eol-style set to native
File size: 19.2 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.osm;
3
4import static org.openstreetmap.josm.tools.I18n.tr;
5
6import java.util.ArrayList;
7import java.util.Collection;
8import java.util.HashMap;
9import java.util.HashSet;
10import java.util.Iterator;
11import java.util.LinkedList;
12import java.util.List;
13import java.util.Map;
14import java.util.Set;
15
16import org.openstreetmap.josm.data.conflict.Conflict;
17import org.openstreetmap.josm.data.conflict.ConflictCollection;
18import org.openstreetmap.josm.gui.progress.ProgressMonitor;
19import org.openstreetmap.josm.tools.CheckParameterUtil;
20
21/**
22 * A dataset merger which takes a target and a source dataset and merges the source data set
23 * onto the target dataset.
24 *
25 */
26public class DataSetMerger {
27
28 /** the collection of conflicts created during merging */
29 private final ConflictCollection conflicts;
30
31 /** the target dataset for merging */
32 private final DataSet targetDataSet;
33 /** the source dataset where primitives are merged from */
34 private final DataSet sourceDataSet;
35
36 /**
37 * A map of all primitives that got replaced with other primitives.
38 * Key is the PrimitiveId in their dataset, the value is the PrimitiveId in my dataset
39 */
40 private final Map<PrimitiveId, PrimitiveId> mergedMap;
41 /** a set of primitive ids for which we have to fix references (to nodes and
42 * to relation members) after the first phase of merging
43 */
44 private final Set<PrimitiveId> objectsWithChildrenToMerge;
45 private final Set<OsmPrimitive> objectsToDelete;
46
47 /**
48 * constructor
49 *
50 * The visitor will merge <code>sourceDataSet</code> onto <code>targetDataSet</code>
51 *
52 * @param targetDataSet dataset with my primitives. Must not be null.
53 * @param sourceDataSet dataset with their primitives. Ignored, if null.
54 * @throws IllegalArgumentException if myDataSet is null
55 */
56 public DataSetMerger(DataSet targetDataSet, DataSet sourceDataSet) {
57 CheckParameterUtil.ensureParameterNotNull(targetDataSet, "targetDataSet");
58 this.targetDataSet = targetDataSet;
59 this.sourceDataSet = sourceDataSet;
60 conflicts = new ConflictCollection();
61 mergedMap = new HashMap<>();
62 objectsWithChildrenToMerge = new HashSet<>();
63 objectsToDelete = new HashSet<>();
64 }
65
66 /**
67 * Merges a primitive onto primitives dataset.
68 *
69 * If other.id != 0 it tries to merge it with an corresponding primitive from
70 * my dataset with the same id. If this is not possible a conflict is remembered
71 * in {@link #conflicts}.
72 *
73 * If other.id == 0 (new primitive) it tries to find a primitive in my dataset with id == 0 which
74 * is semantically equal. If it finds one it merges its technical attributes onto
75 * my primitive.
76 *
77 * @param source the primitive to merge
78 * @param candidates a set of possible candidates for a new primitive
79 */
80 protected void mergePrimitive(OsmPrimitive source, Collection<? extends OsmPrimitive> candidates) {
81 if (!source.isNew()) {
82 // try to merge onto a matching primitive with the same defined id
83 //
84 if (mergeById(source))
85 return;
86 } else {
87 // ignore deleted primitives from source
88 if (source.isDeleted()) return;
89
90 // try to merge onto a primitive which has no id assigned
91 // yet but which is equal in its semantic attributes
92 //
93 for (OsmPrimitive target : candidates) {
94 if (!target.isNew() || target.isDeleted()) {
95 continue;
96 }
97 if (target.hasEqualSemanticAttributes(source)) {
98 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId());
99 // copy the technical attributes from other version
100 target.setVisible(source.isVisible());
101 target.setUser(source.getUser());
102 target.setRawTimestamp(source.getRawTimestamp());
103 target.setModified(source.isModified());
104 objectsWithChildrenToMerge.add(source.getPrimitiveId());
105 return;
106 }
107 }
108 }
109
110 // If we get here we didn't find a suitable primitive in
111 // the target dataset. Create a clone and add it to the target dataset.
112 //
113 OsmPrimitive target;
114 switch(source.getType()) {
115 case NODE: target = source.isNew() ? new Node() : new Node(source.getId()); break;
116 case WAY: target = source.isNew() ? new Way() : new Way(source.getId()); break;
117 case RELATION: target = source.isNew() ? new Relation() : new Relation(source.getId()); break;
118 default: throw new AssertionError();
119 }
120 target.mergeFrom(source);
121 targetDataSet.addPrimitive(target);
122 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId());
123 objectsWithChildrenToMerge.add(source.getPrimitiveId());
124 }
125
126 protected OsmPrimitive getMergeTarget(OsmPrimitive mergeSource) {
127 PrimitiveId targetId = mergedMap.get(mergeSource.getPrimitiveId());
128 if (targetId == null)
129 return null;
130 return targetDataSet.getPrimitiveById(targetId);
131 }
132
133 protected void addConflict(Conflict<?> c) {
134 c.setMergedMap(mergedMap);
135 conflicts.add(c);
136 }
137
138 protected void addConflict(OsmPrimitive my, OsmPrimitive their) {
139 addConflict(new Conflict<>(my, their));
140 }
141
142 protected void fixIncomplete(Way other) {
143 Way myWay = (Way) getMergeTarget(other);
144 if (myWay == null)
145 throw new RuntimeException(tr("Missing merge target for way with id {0}", other.getUniqueId()));
146 }
147
148 /**
149 * Postprocess the dataset and fix all merged references to point to the actual
150 * data.
151 */
152 public void fixReferences() {
153 for (Way w : sourceDataSet.getWays()) {
154 if (!conflicts.hasConflictForTheir(w) && objectsWithChildrenToMerge.contains(w.getPrimitiveId())) {
155 mergeNodeList(w);
156 fixIncomplete(w);
157 }
158 }
159 for (Relation r : sourceDataSet.getRelations()) {
160 if (!conflicts.hasConflictForTheir(r) && objectsWithChildrenToMerge.contains(r.getPrimitiveId())) {
161 mergeRelationMembers(r);
162 }
163 }
164
165 deleteMarkedObjects();
166 }
167
168 /**
169 * Deleted objects in objectsToDelete set and create conflicts for objects that cannot
170 * be deleted because they're referenced in the target dataset.
171 */
172 protected void deleteMarkedObjects() {
173 boolean flag;
174 do {
175 flag = false;
176 for (Iterator<OsmPrimitive> it = objectsToDelete.iterator(); it.hasNext();) {
177 OsmPrimitive target = it.next();
178 OsmPrimitive source = sourceDataSet.getPrimitiveById(target.getPrimitiveId());
179 if (source == null)
180 throw new RuntimeException(
181 tr("Object of type {0} with id {1} was marked to be deleted, but it''s missing in the source dataset",
182 target.getType(), target.getUniqueId()));
183
184 List<OsmPrimitive> referrers = target.getReferrers();
185 if (referrers.isEmpty()) {
186 resetPrimitive(target);
187 target.mergeFrom(source);
188 target.setDeleted(true);
189 it.remove();
190 flag = true;
191 } else {
192 for (OsmPrimitive referrer : referrers) {
193 // If one of object referrers isn't going to be deleted,
194 // add a conflict and don't delete the object
195 if (!objectsToDelete.contains(referrer)) {
196 addConflict(target, source);
197 it.remove();
198 flag = true;
199 break;
200 }
201 }
202 }
203
204 }
205 } while (flag);
206
207 if (!objectsToDelete.isEmpty()) {
208 // There are some more objects rest in the objectsToDelete set
209 // This can be because of cross-referenced relations.
210 for (OsmPrimitive osm: objectsToDelete) {
211 resetPrimitive(osm);
212 }
213 for (OsmPrimitive osm: objectsToDelete) {
214 osm.setDeleted(true);
215 osm.mergeFrom(sourceDataSet.getPrimitiveById(osm.getPrimitiveId()));
216 }
217 }
218 }
219
220 private static void resetPrimitive(OsmPrimitive osm) {
221 if (osm instanceof Way) {
222 ((Way) osm).setNodes(null);
223 } else if (osm instanceof Relation) {
224 ((Relation) osm).setMembers(null);
225 }
226 }
227
228 /**
229 * Merges the node list of a source way onto its target way.
230 *
231 * @param source the source way
232 * @throws IllegalStateException if no target way can be found for the source way
233 * @throws IllegalStateException if there isn't a target node for one of the nodes in the source way
234 *
235 */
236 private void mergeNodeList(Way source) {
237 Way target = (Way) getMergeTarget(source);
238 if (target == null)
239 throw new IllegalStateException(tr("Missing merge target for way with id {0}", source.getUniqueId()));
240
241 List<Node> newNodes = new ArrayList<>(source.getNodesCount());
242 for (Node sourceNode : source.getNodes()) {
243 Node targetNode = (Node) getMergeTarget(sourceNode);
244 if (targetNode != null) {
245 newNodes.add(targetNode);
246 if (targetNode.isDeleted() && !conflicts.hasConflictForMy(targetNode)) {
247 addConflict(new Conflict<OsmPrimitive>(targetNode, sourceNode, true));
248 targetNode.setDeleted(false);
249 }
250 } else
251 throw new IllegalStateException(tr("Missing merge target for node with id {0}", sourceNode.getUniqueId()));
252 }
253 target.setNodes(newNodes);
254 }
255
256 /**
257 * Merges the relation members of a source relation onto the corresponding target relation.
258 * @param source the source relation
259 * @throws IllegalStateException if there is no corresponding target relation
260 * @throws IllegalStateException if there isn't a corresponding target object for one of the relation
261 * members in source
262 */
263 private void mergeRelationMembers(Relation source) {
264 Relation target = (Relation) getMergeTarget(source);
265 if (target == null)
266 throw new IllegalStateException(tr("Missing merge target for relation with id {0}", source.getUniqueId()));
267 List<RelationMember> newMembers = new LinkedList<>();
268 for (RelationMember sourceMember : source.getMembers()) {
269 OsmPrimitive targetMember = getMergeTarget(sourceMember.getMember());
270 if (targetMember == null)
271 throw new IllegalStateException(tr("Missing merge target of type {0} with id {1}",
272 sourceMember.getType(), sourceMember.getUniqueId()));
273 RelationMember newMember = new RelationMember(sourceMember.getRole(), targetMember);
274 newMembers.add(newMember);
275 if (targetMember.isDeleted() && !conflicts.hasConflictForMy(targetMember)) {
276 addConflict(new Conflict<>(targetMember, sourceMember.getMember(), true));
277 targetMember.setDeleted(false);
278 }
279 }
280 target.setMembers(newMembers);
281 }
282
283 /**
284 * Tries to merge a primitive <code>source</code> into an existing primitive with the same id.
285 *
286 * @param source the source primitive which is to be merged into a target primitive
287 * @return true, if this method was able to merge <code>source</code> into a target object; false, otherwise
288 */
289 private boolean mergeById(OsmPrimitive source) {
290 OsmPrimitive target = targetDataSet.getPrimitiveById(source.getId(), source.getType());
291 // merge other into an existing primitive with the same id, if possible
292 //
293 if (target == null)
294 return false;
295 // found a corresponding target, remember it
296 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId());
297
298 if (target.getVersion() > source.getVersion())
299 // target.version > source.version => keep target version
300 return true;
301
302 if (target.isIncomplete() && !source.isIncomplete()) {
303 // target is incomplete, source completes it
304 // => merge source into target
305 //
306 target.mergeFrom(source);
307 objectsWithChildrenToMerge.add(source.getPrimitiveId());
308 } else if (!target.isIncomplete() && source.isIncomplete()) {
309 // target is complete and source is incomplete
310 // => keep target, it has more information already
311 //
312 } else if (target.isIncomplete() && source.isIncomplete()) {
313 // target and source are incomplete. Doesn't matter which one to
314 // take. We take target.
315 //
316 } else if (!target.isModified() && !source.isModified() && target.isVisible() != source.isVisible()
317 && target.getVersion() == source.getVersion())
318 // Same version, but different "visible" attribute and neither of them are modified.
319 // It indicates a serious problem in datasets.
320 // For example, datasets can be fetched from different OSM servers or badly hand-modified.
321 // We shouldn't merge that datasets.
322 throw new DataIntegrityProblemException(tr("Conflict in ''visible'' attribute for object of type {0} with id {1}",
323 target.getType(), target.getId()));
324 else if (target.isDeleted() && !source.isDeleted() && target.getVersion() == source.getVersion()) {
325 // same version, but target is deleted. Assume target takes precedence
326 // otherwise too many conflicts when refreshing from the server
327 // but, if source has a referrer that is not in the target dataset there is a conflict
328 // If target dataset refers to the deleted primitive, conflict will be added in fixReferences method
329 for (OsmPrimitive referrer: source.getReferrers()) {
330 if (targetDataSet.getPrimitiveById(referrer.getPrimitiveId()) == null) {
331 addConflict(new Conflict<>(target, source, true));
332 target.setDeleted(false);
333 break;
334 }
335 }
336 } else if (!target.isModified() && source.isDeleted()) {
337 // target not modified. We can assume that source is the most recent version,
338 // so mark it to be deleted.
339 //
340 objectsToDelete.add(target);
341 } else if (!target.isModified() && source.isModified()) {
342 // target not modified. We can assume that source is the most recent version.
343 // clone it into target.
344 target.mergeFrom(source);
345 objectsWithChildrenToMerge.add(source.getPrimitiveId());
346 } else if (!target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) {
347 // both not modified. Merge nevertheless.
348 // This helps when updating "empty" relations, see #4295
349 target.mergeFrom(source);
350 objectsWithChildrenToMerge.add(source.getPrimitiveId());
351 } else if (!target.isModified() && !source.isModified() && target.getVersion() < source.getVersion()) {
352 // my not modified but other is newer. clone other onto mine.
353 //
354 target.mergeFrom(source);
355 objectsWithChildrenToMerge.add(source.getPrimitiveId());
356 } else if (target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) {
357 // target is same as source but target is modified
358 // => keep target and reset modified flag if target and source are semantically equal
359 if (target.hasEqualSemanticAttributes(source, false)) {
360 target.setModified(false);
361 }
362 } else if (source.isDeleted() != target.isDeleted()) {
363 // target is modified and deleted state differs.
364 // this have to be resolved manually.
365 //
366 addConflict(target, source);
367 } else if (!target.hasEqualSemanticAttributes(source)) {
368 // target is modified and is not semantically equal with source. Can't automatically
369 // resolve the differences
370 // => create a conflict
371 addConflict(target, source);
372 } else {
373 // clone from other. mergeFrom will mainly copy
374 // technical attributes like timestamp or user information. Semantic
375 // attributes should already be equal if we get here.
376 //
377 target.mergeFrom(source);
378 objectsWithChildrenToMerge.add(source.getPrimitiveId());
379 }
380 return true;
381 }
382
383 /**
384 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in
385 * {@link #getTargetDataSet()}.
386 *
387 * See {@link #getConflicts()} for a map of conflicts after the merge operation.
388 */
389 public void merge() {
390 merge(null);
391 }
392
393 /**
394 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in
395 * {@link #getTargetDataSet()}.
396 *
397 * See {@link #getConflicts()} for a map of conflicts after the merge operation.
398 * @param progressMonitor The progress monitor
399 */
400 public void merge(ProgressMonitor progressMonitor) {
401 if (sourceDataSet == null)
402 return;
403 if (progressMonitor != null) {
404 progressMonitor.beginTask(tr("Merging data..."), sourceDataSet.allPrimitives().size());
405 }
406 targetDataSet.beginUpdate();
407 try {
408 List<? extends OsmPrimitive> candidates = new ArrayList<>(targetDataSet.getNodes());
409 for (Node node: sourceDataSet.getNodes()) {
410 mergePrimitive(node, candidates);
411 if (progressMonitor != null) {
412 progressMonitor.worked(1);
413 }
414 }
415 candidates.clear();
416 candidates = new ArrayList<>(targetDataSet.getWays());
417 for (Way way: sourceDataSet.getWays()) {
418 mergePrimitive(way, candidates);
419 if (progressMonitor != null) {
420 progressMonitor.worked(1);
421 }
422 }
423 candidates.clear();
424 candidates = new ArrayList<>(targetDataSet.getRelations());
425 for (Relation relation: sourceDataSet.getRelations()) {
426 mergePrimitive(relation, candidates);
427 if (progressMonitor != null) {
428 progressMonitor.worked(1);
429 }
430 }
431 candidates.clear();
432 fixReferences();
433 } finally {
434 targetDataSet.endUpdate();
435 }
436 if (progressMonitor != null) {
437 progressMonitor.finishTask();
438 }
439 }
440
441 /**
442 * replies my dataset
443 *
444 * @return the own (target) data set
445 */
446 public DataSet getTargetDataSet() {
447 return targetDataSet;
448 }
449
450 /**
451 * replies the map of conflicts
452 *
453 * @return the map of conflicts
454 */
455 public ConflictCollection getConflicts() {
456 return conflicts;
457 }
458}
Note: See TracBrowser for help on using the repository browser.