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 if myDataSet is null 055 */ 056 public DataSetMerger(DataSet targetDataSet, DataSet sourceDataSet) { 057 CheckParameterUtil.ensureParameterNotNull(targetDataSet, "targetDataSet"); 058 this.targetDataSet = targetDataSet; 059 this.sourceDataSet = sourceDataSet; 060 conflicts = new ConflictCollection(); 061 mergedMap = new HashMap<>(); 062 objectsWithChildrenToMerge = new HashSet<>(); 063 objectsToDelete = new HashSet<>(); 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.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}