001 // License: GPL. For details, see LICENSE file. 002 package org.openstreetmap.josm.data.osm; 003 004 import static org.openstreetmap.josm.tools.I18n.tr; 005 006 import java.util.ArrayList; 007 import java.util.Collection; 008 import java.util.HashMap; 009 import java.util.HashSet; 010 import java.util.Iterator; 011 import java.util.LinkedList; 012 import java.util.List; 013 import java.util.Map; 014 import java.util.Set; 015 016 import org.openstreetmap.josm.data.conflict.Conflict; 017 import org.openstreetmap.josm.data.conflict.ConflictCollection; 018 import org.openstreetmap.josm.gui.progress.ProgressMonitor; 019 import org.openstreetmap.josm.tools.CheckParameterUtil; 020 021 /** 022 * A dataset merger which takes a target and a source dataset and merges the source data set 023 * onto the target dataset. 024 * 025 */ 026 public class DataSetMerger { 027 028 /** the collection of conflicts created during merging */ 029 private final ConflictCollection conflicts; 030 031 /** the target dataset for merging */ 032 private final DataSet targetDataSet; 033 /** the source dataset where primitives are merged from */ 034 private final DataSet sourceDataSet; 035 036 /** 037 * A map of all primitives that got replaced with other primitives. 038 * Key is the PrimitiveId in their dataset, the value is the PrimitiveId in my dataset 039 */ 040 private final Map<PrimitiveId, PrimitiveId> mergedMap; 041 /** a set of primitive ids for which we have to fix references (to nodes and 042 * to relation members) after the first phase of merging 043 */ 044 private final Set<PrimitiveId> objectsWithChildrenToMerge; 045 private final Set<OsmPrimitive> objectsToDelete; 046 047 /** 048 * constructor 049 * 050 * The visitor will merge <code>theirDataSet</code> onto <code>myDataSet</code> 051 * 052 * @param targetDataSet dataset with my primitives. Must not be null. 053 * @param sourceDataSet dataset with their primitives. Ignored, if null. 054 * @throws IllegalArgumentException thrown if myDataSet is null 055 */ 056 public DataSetMerger(DataSet targetDataSet, DataSet sourceDataSet) throws IllegalArgumentException { 057 CheckParameterUtil.ensureParameterNotNull(targetDataSet, "targetDataSet"); 058 this.targetDataSet = targetDataSet; 059 this.sourceDataSet = sourceDataSet; 060 conflicts = new ConflictCollection(); 061 mergedMap = new HashMap<PrimitiveId, PrimitiveId>(); 062 objectsWithChildrenToMerge = new HashSet<PrimitiveId>(); 063 objectsToDelete = new HashSet<OsmPrimitive>(); 064 } 065 066 /** 067 * Merges a primitive <code>other</code> of type <P> onto my primitives. 068 * 069 * If other.id != 0 it tries to merge it with an corresponding primitive from 070 * my dataset with the same id. If this is not possible a conflict is remembered 071 * in {@link #conflicts}. 072 * 073 * If other.id == 0 it tries to find a primitive in my dataset with id == 0 which 074 * is semantically equal. If it finds one it merges its technical attributes onto 075 * my primitive. 076 * 077 * @param <P> the type of the other primitive 078 * @param source the other primitive 079 */ 080 protected void mergePrimitive(OsmPrimitive source, Collection<? extends OsmPrimitive> candidates) { 081 if (!source.isNew() ) { 082 // try to merge onto a matching primitive with the same 083 // defined id 084 // 085 if (mergeById(source)) 086 return; 087 //if (!source.isVisible()) 088 // ignore it 089 // return; 090 } else { 091 // ignore deleted primitives from source 092 if (source.isDeleted()) return; 093 094 // try to merge onto a primitive which has no id assigned 095 // yet but which is equal in its semantic attributes 096 // 097 for (OsmPrimitive target : candidates) { 098 if (!target.isNew() || target.isDeleted()) { 099 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 }