001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.osm; 003 004import static org.openstreetmap.josm.tools.I18n.tr; 005 006import java.util.ArrayList; 007import java.util.Collection; 008import java.util.HashMap; 009import java.util.HashSet; 010import java.util.Iterator; 011import java.util.LinkedList; 012import java.util.List; 013import java.util.Map; 014import java.util.Set; 015 016import org.openstreetmap.josm.data.conflict.Conflict; 017import org.openstreetmap.josm.data.conflict.ConflictCollection; 018import org.openstreetmap.josm.gui.progress.ProgressMonitor; 019import 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 */ 026public 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>sourceDataSet</code> onto <code>targetDataSet</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 onto primitives dataset. 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 (new primitive) 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 source the primitive to merge 078 * @param candidates a set of possible candidates for a new 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 defined id 083 // 084 if (mergeById(source)) 085 return; 086 } else { 087 // ignore deleted primitives from source 088 if (source.isDeleted()) return; 089 090 // try to merge onto a primitive which has no id assigned 091 // yet but which is equal in its semantic attributes 092 // 093 for (OsmPrimitive target : candidates) { 094 if (!target.isNew() || target.isDeleted()) { 095 continue; 096 } 097 if (target.hasEqualSemanticAttributes(source)) { 098 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId()); 099 // copy the technical attributes from other version 100 target.setVisible(source.isVisible()); 101 target.setUser(source.getUser()); 102 target.setTimestamp(source.getTimestamp()); 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 = null; 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) throws IllegalStateException { 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<OsmPrimitive>(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(tr("Object of type {0} with id {1} was marked to be deleted, but it''s missing in the source dataset", 181 target.getType(), target.getUniqueId())); 182 183 List<OsmPrimitive> referrers = target.getReferrers(); 184 if (referrers.isEmpty()) { 185 resetPrimitive(target); 186 target.mergeFrom(source); 187 target.setDeleted(true); 188 it.remove(); 189 flag = true; 190 } else { 191 for (OsmPrimitive referrer : referrers) { 192 // If one of object referrers isn't going to be deleted, 193 // add a conflict and don't delete the object 194 if (!objectsToDelete.contains(referrer)) { 195 addConflict(target, source); 196 it.remove(); 197 flag = true; 198 break; 199 } 200 } 201 } 202 203 } 204 } while (flag); 205 206 if (!objectsToDelete.isEmpty()) { 207 // There are some more objects rest in the objectsToDelete set 208 // This can be because of cross-referenced relations. 209 for (OsmPrimitive osm: objectsToDelete) { 210 resetPrimitive(osm); 211 } 212 for (OsmPrimitive osm: objectsToDelete) { 213 osm.setDeleted(true); 214 osm.mergeFrom(sourceDataSet.getPrimitiveById(osm.getPrimitiveId())); 215 } 216 } 217 } 218 219 private final void resetPrimitive(OsmPrimitive osm) { 220 if (osm instanceof Way) { 221 ((Way) osm).setNodes(null); 222 } else if (osm instanceof Relation) { 223 ((Relation) osm).setMembers(null); 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 #getTargetDataSet()}. 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 #getTargetDataSet()}. 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 List<? 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 the own (target) data set 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}