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

Last change on this file since 5350 was 5350, checked in by Don-vip, 12 years ago

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