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

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

see #4899, see #7266, see #7333: Resolved NPE in conflict manager when copying a member created by merging two layers
  • Property svn:eol-style set to native
File size: 19.4 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 target.setDeleted(true);
191 target.mergeFrom(source);
192 it.remove();
193 flag = true;
194 } else {
195 for (OsmPrimitive referrer : referrers) {
196 // If one of object referrers isn't going to be deleted,
197 // add a conflict and don't delete the object
198 if (!objectsToDelete.contains(referrer)) {
199 addConflict(target, source);
200 it.remove();
201 flag = true;
202 break;
203 }
204 }
205 }
206
207 }
208 } while (flag);
209
210 if (!objectsToDelete.isEmpty()) {
211 // There are some more objects rest in the objectsToDelete set
212 // This can be because of cross-referenced relations.
213 for (OsmPrimitive osm: objectsToDelete) {
214 if (osm instanceof Way) {
215 ((Way) osm).setNodes(null);
216 } else if (osm instanceof Relation) {
217 ((Relation) osm).setMembers(null);
218 }
219 }
220 for (OsmPrimitive osm: objectsToDelete) {
221 osm.setDeleted(true);
222 osm.mergeFrom(sourceDataSet.getPrimitiveById(osm.getPrimitiveId()));
223 }
224 }
225 }
226
227 /**
228 * Merges the node list of a source way onto its target way.
229 *
230 * @param source the source way
231 * @throws IllegalStateException thrown if no target way can be found for the source way
232 * @throws IllegalStateException thrown if there isn't a target node for one of the nodes in the source way
233 *
234 */
235 private void mergeNodeList(Way source) throws IllegalStateException {
236 Way target = (Way)getMergeTarget(source);
237 if (target == null)
238 throw new IllegalStateException(tr("Missing merge target for way with id {0}", source.getUniqueId()));
239
240 List<Node> newNodes = new ArrayList<Node>(source.getNodesCount());
241 for (Node sourceNode : source.getNodes()) {
242 Node targetNode = (Node)getMergeTarget(sourceNode);
243 if (targetNode != null) {
244 newNodes.add(targetNode);
245 if (targetNode.isDeleted() && !conflicts.hasConflictForMy(targetNode)) {
246 addConflict(new Conflict<OsmPrimitive>(targetNode, sourceNode, true));
247 targetNode.setDeleted(false);
248 }
249 } else
250 throw new IllegalStateException(tr("Missing merge target for node with id {0}", sourceNode.getUniqueId()));
251 }
252 target.setNodes(newNodes);
253 }
254
255 /**
256 * Merges the relation members of a source relation onto the corresponding target relation.
257 * @param source the source relation
258 * @throws IllegalStateException thrown if there is no corresponding target relation
259 * @throws IllegalStateException thrown if there isn't a corresponding target object for one of the relation
260 * members in source
261 */
262 private void mergeRelationMembers(Relation source) throws IllegalStateException {
263 Relation target = (Relation) getMergeTarget(source);
264 if (target == null)
265 throw new IllegalStateException(tr("Missing merge target for relation with id {0}", source.getUniqueId()));
266 LinkedList<RelationMember> newMembers = new LinkedList<RelationMember>();
267 for (RelationMember sourceMember : source.getMembers()) {
268 OsmPrimitive targetMember = getMergeTarget(sourceMember.getMember());
269 if (targetMember == null)
270 throw new IllegalStateException(tr("Missing merge target of type {0} with id {1}", sourceMember.getType(), sourceMember.getUniqueId()));
271 RelationMember newMember = new RelationMember(sourceMember.getRole(), targetMember);
272 newMembers.add(newMember);
273 if (targetMember.isDeleted() && !conflicts.hasConflictForMy(targetMember)) {
274 addConflict(new Conflict<OsmPrimitive>(targetMember, sourceMember.getMember(), true));
275 targetMember.setDeleted(false);
276 }
277 }
278 target.setMembers(newMembers);
279 }
280
281 /**
282 * Tries to merge a primitive <code>source</code> into an existing primitive with the same id.
283 *
284 * @param source the source primitive which is to be merged into a target primitive
285 * @return true, if this method was able to merge <code>source</code> into a target object; false, otherwise
286 */
287 private boolean mergeById(OsmPrimitive source) {
288 OsmPrimitive target = targetDataSet.getPrimitiveById(source.getId(), source.getType());
289 // merge other into an existing primitive with the same id, if possible
290 //
291 if (target == null)
292 return false;
293 // found a corresponding target, remember it
294 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId());
295
296 if (target.getVersion() > source.getVersion())
297 // target.version > source.version => keep target version
298 return true;
299
300 if (target.isIncomplete() && !source.isIncomplete()) {
301 // target is incomplete, source completes it
302 // => merge source into target
303 //
304 target.mergeFrom(source);
305 objectsWithChildrenToMerge.add(source.getPrimitiveId());
306 } else if (!target.isIncomplete() && source.isIncomplete()) {
307 // target is complete and source is incomplete
308 // => keep target, it has more information already
309 //
310 } else if (target.isIncomplete() && source.isIncomplete()) {
311 // target and source are incomplete. Doesn't matter which one to
312 // take. We take target.
313 //
314 } else if (!target.isModified() && !source.isModified() && target.isVisible() != source.isVisible() && target.getVersion() == source.getVersion())
315 // Same version, but different "visible" attribute and neither of them are modified.
316 // It indicates a serious problem in datasets.
317 // For example, datasets can be fetched from different OSM servers or badly hand-modified.
318 // We shouldn't merge that datasets.
319 throw new DataIntegrityProblemException(tr("Conflict in ''visible'' attribute for object of type {0} with id {1}",
320 target.getType(), target.getId()));
321 else if (target.isDeleted() && ! source.isDeleted() && target.getVersion() == source.getVersion()) {
322 // same version, but target is deleted. Assume target takes precedence
323 // otherwise too many conflicts when refreshing from the server
324 // but, if source has a referrer that is not in the target dataset there is a conflict
325 // If target dataset refers to the deleted primitive, conflict will be added in fixReferences method
326 for (OsmPrimitive referrer: source.getReferrers()) {
327 if (targetDataSet.getPrimitiveById(referrer.getPrimitiveId()) == null) {
328 addConflict(new Conflict<OsmPrimitive>(target, source, true));
329 target.setDeleted(false);
330 break;
331 }
332 }
333 } else if (! target.isModified() && source.isDeleted()) {
334 // target not modified. We can assume that source is the most recent version,
335 // so mark it to be deleted.
336 //
337 objectsToDelete.add(target);
338 } else if (! target.isModified() && source.isModified()) {
339 // target not modified. We can assume that source is the most recent version.
340 // clone it into target.
341 target.mergeFrom(source);
342 objectsWithChildrenToMerge.add(source.getPrimitiveId());
343 } else if (! target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) {
344 // both not modified. Merge nevertheless.
345 // This helps when updating "empty" relations, see #4295
346 target.mergeFrom(source);
347 objectsWithChildrenToMerge.add(source.getPrimitiveId());
348 } else if (! target.isModified() && !source.isModified() && target.getVersion() < source.getVersion()) {
349 // my not modified but other is newer. clone other onto mine.
350 //
351 target.mergeFrom(source);
352 objectsWithChildrenToMerge.add(source.getPrimitiveId());
353 } else if (target.isModified() && ! source.isModified() && target.getVersion() == source.getVersion()) {
354 // target is same as source but target is modified
355 // => keep target and reset modified flag if target and source are semantically equal
356 if (target.hasEqualSemanticAttributes(source)) {
357 target.setModified(false);
358 }
359 } else if (source.isDeleted() != target.isDeleted()) {
360 // target is modified and deleted state differs.
361 // this have to be resolved manually.
362 //
363 addConflict(target,source);
364 } else if (! target.hasEqualSemanticAttributes(source)) {
365 // target is modified and is not semantically equal with source. Can't automatically
366 // resolve the differences
367 // => create a conflict
368 addConflict(target,source);
369 } else {
370 // clone from other. mergeFrom will mainly copy
371 // technical attributes like timestamp or user information. Semantic
372 // attributes should already be equal if we get here.
373 //
374 target.mergeFrom(source);
375 objectsWithChildrenToMerge.add(source.getPrimitiveId());
376 }
377 return true;
378 }
379
380 /**
381 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in
382 * {@link #getMyDataSet()}.
383 *
384 * See {@link #getConflicts()} for a map of conflicts after the merge operation.
385 */
386 public void merge() {
387 merge(null);
388 }
389
390 /**
391 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in
392 * {@link #getMyDataSet()}.
393 *
394 * See {@link #getConflicts()} for a map of conflicts after the merge operation.
395 */
396 public void merge(ProgressMonitor progressMonitor) {
397 if (sourceDataSet == null)
398 return;
399 if (progressMonitor != null) {
400 progressMonitor.beginTask(tr("Merging data..."), sourceDataSet.allPrimitives().size());
401 }
402 targetDataSet.beginUpdate();
403 try {
404 ArrayList<? extends OsmPrimitive> candidates = new ArrayList<Node>(targetDataSet.getNodes());
405 for (Node node: sourceDataSet.getNodes()) {
406 mergePrimitive(node, candidates);
407 if (progressMonitor != null) {
408 progressMonitor.worked(1);
409 }
410 }
411 candidates.clear();
412 candidates = new ArrayList<Way>(targetDataSet.getWays());
413 for (Way way: sourceDataSet.getWays()) {
414 mergePrimitive(way, candidates);
415 if (progressMonitor != null) {
416 progressMonitor.worked(1);
417 }
418 }
419 candidates.clear();
420 candidates = new ArrayList<Relation>(targetDataSet.getRelations());
421 for (Relation relation: sourceDataSet.getRelations()) {
422 mergePrimitive(relation, candidates);
423 if (progressMonitor != null) {
424 progressMonitor.worked(1);
425 }
426 }
427 candidates.clear();
428 fixReferences();
429 } finally {
430 targetDataSet.endUpdate();
431 }
432 if (progressMonitor != null) {
433 progressMonitor.finishTask();
434 }
435 }
436
437 /**
438 * replies my dataset
439 *
440 * @return
441 */
442 public DataSet getTargetDataSet() {
443 return targetDataSet;
444 }
445
446 /**
447 * replies the map of conflicts
448 *
449 * @return the map of conflicts
450 */
451 public ConflictCollection getConflicts() {
452 return conflicts;
453 }
454}
Note: See TracBrowser for help on using the repository browser.