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.awt.geom.Area; 007import java.util.ArrayList; 008import java.util.Collection; 009import java.util.HashMap; 010import java.util.HashSet; 011import java.util.Iterator; 012import java.util.LinkedList; 013import java.util.List; 014import java.util.Map; 015import java.util.Set; 016 017import org.openstreetmap.josm.data.DataSource; 018import org.openstreetmap.josm.data.conflict.Conflict; 019import org.openstreetmap.josm.data.conflict.ConflictCollection; 020import org.openstreetmap.josm.gui.progress.ProgressMonitor; 021import org.openstreetmap.josm.tools.CheckParameterUtil; 022import org.openstreetmap.josm.tools.JosmRuntimeException; 023 024/** 025 * A dataset merger which takes a target and a source dataset and merges the source data set 026 * onto the target dataset. 027 * 028 */ 029public class DataSetMerger { 030 031 /** the collection of conflicts created during merging */ 032 private final ConflictCollection conflicts; 033 034 /** the target dataset for merging */ 035 private final DataSet targetDataSet; 036 /** the source dataset where primitives are merged from */ 037 private final DataSet sourceDataSet; 038 039 /** 040 * A map of all primitives that got replaced with other primitives. 041 * Key is the PrimitiveId in their dataset, the value is the PrimitiveId in my dataset 042 */ 043 private final Map<PrimitiveId, PrimitiveId> mergedMap; 044 /** a set of primitive ids for which we have to fix references (to nodes and 045 * to relation members) after the first phase of merging 046 */ 047 private final Set<PrimitiveId> objectsWithChildrenToMerge; 048 private final Set<OsmPrimitive> objectsToDelete; 049 050 /** 051 * constructor 052 * 053 * The visitor will merge <code>sourceDataSet</code> onto <code>targetDataSet</code> 054 * 055 * @param targetDataSet dataset with my primitives. Must not be null. 056 * @param sourceDataSet dataset with their primitives. Ignored, if null. 057 * @throws IllegalArgumentException if myDataSet is null 058 */ 059 public DataSetMerger(DataSet targetDataSet, DataSet sourceDataSet) { 060 CheckParameterUtil.ensureParameterNotNull(targetDataSet, "targetDataSet"); 061 this.targetDataSet = targetDataSet; 062 this.sourceDataSet = sourceDataSet; 063 conflicts = new ConflictCollection(); 064 mergedMap = new HashMap<>(); 065 objectsWithChildrenToMerge = new HashSet<>(); 066 objectsToDelete = new HashSet<>(); 067 } 068 069 /** 070 * Merges a primitive onto primitives dataset. 071 * 072 * If other.id != 0 it tries to merge it with an corresponding primitive from 073 * my dataset with the same id. If this is not possible a conflict is remembered 074 * in {@link #conflicts}. 075 * 076 * If other.id == 0 (new primitive) it tries to find a primitive in my dataset with id == 0 which 077 * is semantically equal. If it finds one it merges its technical attributes onto 078 * my primitive. 079 * 080 * @param source the primitive to merge 081 * @param candidates a set of possible candidates for a new primitive 082 */ 083 protected void mergePrimitive(OsmPrimitive source, Collection<? extends OsmPrimitive> candidates) { 084 if (!source.isNew()) { 085 // try to merge onto a matching primitive with the same defined id 086 // 087 if (mergeById(source)) 088 return; 089 } else { 090 // ignore deleted primitives from source 091 if (source.isDeleted()) return; 092 093 // try to merge onto a primitive which has no id assigned 094 // yet but which is equal in its semantic attributes 095 // 096 for (OsmPrimitive target : candidates) { 097 if (!target.isNew() || target.isDeleted()) { 098 continue; 099 } 100 if (target.hasEqualSemanticAttributes(source)) { 101 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId()); 102 // copy the technical attributes from other version 103 target.setVisible(source.isVisible()); 104 target.setUser(source.getUser()); 105 target.setRawTimestamp(source.getRawTimestamp()); 106 target.setModified(source.isModified()); 107 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 108 return; 109 } 110 } 111 } 112 113 // If we get here we didn't find a suitable primitive in 114 // the target dataset. Create a clone and add it to the target dataset. 115 // 116 OsmPrimitive target; 117 switch(source.getType()) { 118 case NODE: target = source.isNew() ? new Node() : new Node(source.getId()); break; 119 case WAY: target = source.isNew() ? new Way() : new Way(source.getId()); break; 120 case RELATION: target = source.isNew() ? new Relation() : new Relation(source.getId()); break; 121 default: throw new AssertionError(); 122 } 123 target.mergeFrom(source); 124 targetDataSet.addPrimitive(target); 125 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId()); 126 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 127 } 128 129 protected OsmPrimitive getMergeTarget(OsmPrimitive mergeSource) { 130 PrimitiveId targetId = mergedMap.get(mergeSource.getPrimitiveId()); 131 if (targetId == null) 132 return null; 133 return targetDataSet.getPrimitiveById(targetId); 134 } 135 136 protected void addConflict(Conflict<?> c) { 137 c.setMergedMap(mergedMap); 138 conflicts.add(c); 139 } 140 141 protected void addConflict(OsmPrimitive my, OsmPrimitive their) { 142 addConflict(new Conflict<>(my, their)); 143 } 144 145 protected void fixIncomplete(Way other) { 146 Way myWay = (Way) getMergeTarget(other); 147 if (myWay == null) 148 throw new JosmRuntimeException(tr("Missing merge target for way with id {0}", other.getUniqueId())); 149 } 150 151 /** 152 * Postprocess the dataset and fix all merged references to point to the actual 153 * data. 154 */ 155 public void fixReferences() { 156 for (Way w : sourceDataSet.getWays()) { 157 if (!conflicts.hasConflictForTheir(w) && objectsWithChildrenToMerge.contains(w.getPrimitiveId())) { 158 mergeNodeList(w); 159 fixIncomplete(w); 160 } 161 } 162 for (Relation r : sourceDataSet.getRelations()) { 163 if (!conflicts.hasConflictForTheir(r) && objectsWithChildrenToMerge.contains(r.getPrimitiveId())) { 164 mergeRelationMembers(r); 165 } 166 } 167 168 deleteMarkedObjects(); 169 } 170 171 /** 172 * Deleted objects in objectsToDelete set and create conflicts for objects that cannot 173 * be deleted because they're referenced in the target dataset. 174 */ 175 protected void deleteMarkedObjects() { 176 boolean flag; 177 do { 178 flag = false; 179 for (Iterator<OsmPrimitive> it = objectsToDelete.iterator(); it.hasNext();) { 180 OsmPrimitive target = it.next(); 181 OsmPrimitive source = sourceDataSet.getPrimitiveById(target.getPrimitiveId()); 182 if (source == null) 183 throw new JosmRuntimeException( 184 tr("Object of type {0} with id {1} was marked to be deleted, but it''s missing in the source dataset", 185 target.getType(), target.getUniqueId())); 186 187 List<OsmPrimitive> referrers = target.getReferrers(); 188 if (referrers.isEmpty()) { 189 resetPrimitive(target); 190 target.mergeFrom(source); 191 target.setDeleted(true); 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 resetPrimitive(osm); 215 } 216 for (OsmPrimitive osm: objectsToDelete) { 217 osm.setDeleted(true); 218 osm.mergeFrom(sourceDataSet.getPrimitiveById(osm.getPrimitiveId())); 219 } 220 } 221 } 222 223 private static void resetPrimitive(OsmPrimitive osm) { 224 if (osm instanceof Way) { 225 ((Way) osm).setNodes(null); 226 } else if (osm instanceof Relation) { 227 ((Relation) osm).setMembers(null); 228 } 229 } 230 231 /** 232 * Merges the node list of a source way onto its target way. 233 * 234 * @param source the source way 235 * @throws IllegalStateException if no target way can be found for the source way 236 * @throws IllegalStateException if there isn't a target node for one of the nodes in the source way 237 * 238 */ 239 private void mergeNodeList(Way source) { 240 Way target = (Way) getMergeTarget(source); 241 if (target == null) 242 throw new IllegalStateException(tr("Missing merge target for way with id {0}", source.getUniqueId())); 243 244 List<Node> newNodes = new ArrayList<>(source.getNodesCount()); 245 for (Node sourceNode : source.getNodes()) { 246 Node targetNode = (Node) getMergeTarget(sourceNode); 247 if (targetNode != null) { 248 newNodes.add(targetNode); 249 if (targetNode.isDeleted() && !conflicts.hasConflictForMy(targetNode)) { 250 addConflict(new Conflict<OsmPrimitive>(targetNode, sourceNode, true)); 251 targetNode.setDeleted(false); 252 } 253 } else 254 throw new IllegalStateException(tr("Missing merge target for node with id {0}", sourceNode.getUniqueId())); 255 } 256 target.setNodes(newNodes); 257 } 258 259 /** 260 * Merges the relation members of a source relation onto the corresponding target relation. 261 * @param source the source relation 262 * @throws IllegalStateException if there is no corresponding target relation 263 * @throws IllegalStateException if there isn't a corresponding target object for one of the relation 264 * members in source 265 */ 266 private void mergeRelationMembers(Relation source) { 267 Relation target = (Relation) getMergeTarget(source); 268 if (target == null) 269 throw new IllegalStateException(tr("Missing merge target for relation with id {0}", source.getUniqueId())); 270 List<RelationMember> newMembers = new LinkedList<>(); 271 for (RelationMember sourceMember : source.getMembers()) { 272 OsmPrimitive targetMember = getMergeTarget(sourceMember.getMember()); 273 if (targetMember == null) 274 throw new IllegalStateException(tr("Missing merge target of type {0} with id {1}", 275 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<>(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() 320 && target.getVersion() == source.getVersion()) { 321 // Same version, but different "visible" attribute and neither of them are modified. 322 // It indicates a serious problem in datasets. 323 // For example, datasets can be fetched from different OSM servers or badly hand-modified. 324 // We shouldn't merge that datasets. 325 throw new DataIntegrityProblemException(tr("Conflict in ''visible'' attribute for object of type {0} with id {1}", 326 target.getType(), target.getId())); 327 } else if (target.isDeleted() && !source.isDeleted() && target.getVersion() == source.getVersion()) { 328 // same version, but target is deleted. Assume target takes precedence 329 // otherwise too many conflicts when refreshing from the server 330 // but, if source is modified, there is a conflict 331 if (source.isModified()) { 332 addConflict(new Conflict<>(target, source, true)); 333 } 334 // or, if source has a referrer that is not in the target dataset there is a conflict 335 // If target dataset refers to the deleted primitive, conflict will be added in fixReferences method 336 for (OsmPrimitive referrer: source.getReferrers()) { 337 if (targetDataSet.getPrimitiveById(referrer.getPrimitiveId()) == null) { 338 addConflict(new Conflict<>(target, source, true)); 339 target.setDeleted(false); 340 break; 341 } 342 } 343 } else if (!target.isModified() && source.isDeleted()) { 344 // target not modified. We can assume that source is the most recent version, 345 // so mark it to be deleted. 346 // 347 objectsToDelete.add(target); 348 } else if (!target.isModified() && source.isModified()) { 349 // target not modified. We can assume that source is the most recent version. 350 // clone it into target. 351 target.mergeFrom(source); 352 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 353 } else if (!target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) { 354 // both not modified. Merge nevertheless. 355 // This helps when updating "empty" relations, see #4295 356 target.mergeFrom(source); 357 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 358 } else if (!target.isModified() && !source.isModified() && target.getVersion() < source.getVersion()) { 359 // my not modified but other is newer. clone other onto mine. 360 // 361 target.mergeFrom(source); 362 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 363 } else if (target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) { 364 // target is same as source but target is modified 365 // => keep target and reset modified flag if target and source are semantically equal 366 if (target.hasEqualSemanticAttributes(source, false)) { 367 target.setModified(false); 368 } 369 } else if (source.isDeleted() != target.isDeleted()) { 370 // target is modified and deleted state differs. 371 // this have to be resolved manually. 372 // 373 addConflict(target, source); 374 } else if (!target.hasEqualSemanticAttributes(source)) { 375 // target is modified and is not semantically equal with source. Can't automatically 376 // resolve the differences 377 // => create a conflict 378 addConflict(target, source); 379 } else { 380 // clone from other. mergeFrom will mainly copy 381 // technical attributes like timestamp or user information. Semantic 382 // attributes should already be equal if we get here. 383 // 384 target.mergeFrom(source); 385 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 386 } 387 return true; 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() { 397 merge(null); 398 } 399 400 /** 401 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in 402 * {@link #getTargetDataSet()}. 403 * 404 * See {@link #getConflicts()} for a map of conflicts after the merge operation. 405 * @param progressMonitor The progress monitor 406 */ 407 public void merge(ProgressMonitor progressMonitor) { 408 merge(progressMonitor, true); 409 } 410 411 /** 412 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in 413 * {@link #getTargetDataSet()}. 414 * 415 * See {@link #getConflicts()} for a map of conflicts after the merge operation. 416 * @param progressMonitor The progress monitor 417 * @param mergeBounds Whether or not to merge the bounds of the new DataSet to 418 * the existing DataSet 419 * @since 15127 420 */ 421 public void merge(ProgressMonitor progressMonitor, boolean mergeBounds) { 422 if (sourceDataSet == null) 423 return; 424 if (progressMonitor != null) { 425 progressMonitor.beginTask(tr("Merging data..."), sourceDataSet.allPrimitives().size()); 426 } 427 targetDataSet.beginUpdate(); 428 try { 429 List<? extends OsmPrimitive> candidates = new ArrayList<>(targetDataSet.getNodes()); 430 for (Node node: sourceDataSet.getNodes()) { 431 mergePrimitive(node, candidates); 432 if (progressMonitor != null) { 433 progressMonitor.worked(1); 434 } 435 } 436 candidates.clear(); 437 candidates = new ArrayList<>(targetDataSet.getWays()); 438 for (Way way: sourceDataSet.getWays()) { 439 mergePrimitive(way, candidates); 440 if (progressMonitor != null) { 441 progressMonitor.worked(1); 442 } 443 } 444 candidates.clear(); 445 candidates = new ArrayList<>(targetDataSet.getRelations()); 446 for (Relation relation: sourceDataSet.getRelations()) { 447 mergePrimitive(relation, candidates); 448 if (progressMonitor != null) { 449 progressMonitor.worked(1); 450 } 451 } 452 candidates.clear(); 453 fixReferences(); 454 455 Area a = targetDataSet.getDataSourceArea(); 456 457 // copy the merged layer's data source info. 458 // only add source rectangles if they are not contained in the layer already. 459 if (mergeBounds) { 460 for (DataSource src : sourceDataSet.getDataSources()) { 461 if (a == null || !a.contains(src.bounds.asRect())) { 462 targetDataSet.addDataSource(src); 463 } 464 } 465 } 466 467 // copy the merged layer's API version 468 if (targetDataSet.getVersion() == null) { 469 targetDataSet.setVersion(sourceDataSet.getVersion()); 470 } 471 472 // copy the merged layer's policies and locked status 473 if (sourceDataSet.getUploadPolicy() != null && (targetDataSet.getUploadPolicy() == null 474 || sourceDataSet.getUploadPolicy().compareTo(targetDataSet.getUploadPolicy()) > 0)) { 475 targetDataSet.setUploadPolicy(sourceDataSet.getUploadPolicy()); 476 } 477 if (sourceDataSet.getDownloadPolicy() != null && (targetDataSet.getDownloadPolicy() == null 478 || sourceDataSet.getDownloadPolicy().compareTo(targetDataSet.getDownloadPolicy()) > 0)) { 479 targetDataSet.setDownloadPolicy(sourceDataSet.getDownloadPolicy()); 480 } 481 if (sourceDataSet.isLocked() && !targetDataSet.isLocked()) { 482 targetDataSet.lock(); 483 } 484 } finally { 485 targetDataSet.endUpdate(); 486 } 487 if (progressMonitor != null) { 488 progressMonitor.finishTask(); 489 } 490 } 491 492 /** 493 * replies my dataset 494 * 495 * @return the own (target) data set 496 */ 497 public DataSet getTargetDataSet() { 498 return targetDataSet; 499 } 500 501 /** 502 * replies the map of conflicts 503 * 504 * @return the map of conflicts 505 */ 506 public ConflictCollection getConflicts() { 507 return conflicts; 508 } 509}