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 newMembers.add(new RelationMember(sourceMember.getRole(), targetMember)); 277 if (targetMember.isDeleted() && !conflicts.hasConflictForMy(targetMember)) { 278 addConflict(new Conflict<>(targetMember, sourceMember.getMember(), true)); 279 targetMember.setDeleted(false); 280 } 281 } 282 target.setMembers(newMembers); 283 } 284 285 /** 286 * Tries to merge a primitive <code>source</code> into an existing primitive with the same id. 287 * 288 * @param source the source primitive which is to be merged into a target primitive 289 * @return true, if this method was able to merge <code>source</code> into a target object; false, otherwise 290 */ 291 private boolean mergeById(OsmPrimitive source) { 292 OsmPrimitive target = targetDataSet.getPrimitiveById(source.getId(), source.getType()); 293 // merge other into an existing primitive with the same id, if possible 294 // 295 if (target == null) 296 return false; 297 // found a corresponding target, remember it 298 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId()); 299 300 if (target.getVersion() > source.getVersion()) 301 // target.version > source.version => keep target version 302 return true; 303 304 if (target.isIncomplete() && !source.isIncomplete()) { 305 // target is incomplete, source completes it 306 // => merge source into target 307 // 308 target.mergeFrom(source); 309 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 310 } else if (!target.isIncomplete() && source.isIncomplete()) { 311 // target is complete and source is incomplete 312 // => keep target, it has more information already 313 // 314 } else if (target.isIncomplete() && source.isIncomplete()) { 315 // target and source are incomplete. Doesn't matter which one to 316 // take. We take target. 317 // 318 } else if (!target.isModified() && !source.isModified() && target.isVisible() != source.isVisible() 319 && 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 is modified, there is a conflict 330 if (source.isModified()) { 331 addConflict(new Conflict<>(target, source, true)); 332 } 333 // or, if source has a referrer that is not in the target dataset there is a conflict 334 // If target dataset refers to the deleted primitive, conflict will be added in fixReferences method 335 for (OsmPrimitive referrer: source.getReferrers()) { 336 if (targetDataSet.getPrimitiveById(referrer.getPrimitiveId()) == null) { 337 addConflict(new Conflict<>(target, source, true)); 338 target.setDeleted(false); 339 break; 340 } 341 } 342 } else if (!target.isModified() && source.isDeleted()) { 343 // target not modified. We can assume that source is the most recent version, 344 // so mark it to be deleted. 345 // 346 objectsToDelete.add(target); 347 } else if (!target.isModified() && source.isModified()) { 348 // target not modified. We can assume that source is the most recent version. 349 // clone it into target. 350 target.mergeFrom(source); 351 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 352 } else if (!target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) { 353 // both not modified. Merge nevertheless. 354 // This helps when updating "empty" relations, see #4295 355 target.mergeFrom(source); 356 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 357 } else if (!target.isModified() && !source.isModified() && target.getVersion() < source.getVersion()) { 358 // my not modified but other is newer. clone other onto mine. 359 // 360 target.mergeFrom(source); 361 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 362 } else if (target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) { 363 // target is same as source but target is modified 364 // => keep target and reset modified flag if target and source are semantically equal 365 if (target.hasEqualSemanticAttributes(source, false)) { 366 target.setModified(false); 367 } 368 } else if (source.isDeleted() != target.isDeleted()) { 369 // target is modified and deleted state differs. 370 // this have to be resolved manually. 371 // 372 addConflict(target, source); 373 } else if (!target.hasEqualSemanticAttributes(source)) { 374 // target is modified and is not semantically equal with source. Can't automatically 375 // resolve the differences 376 // => create a conflict 377 addConflict(target, source); 378 } else { 379 // clone from other. mergeFrom will mainly copy 380 // technical attributes like timestamp or user information. Semantic 381 // attributes should already be equal if we get here. 382 // 383 target.mergeFrom(source); 384 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 385 } 386 return true; 387 } 388 389 /** 390 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in 391 * {@link #getTargetDataSet()}. 392 * 393 * See {@link #getConflicts()} for a map of conflicts after the merge operation. 394 */ 395 public void merge() { 396 merge(null); 397 } 398 399 /** 400 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in 401 * {@link #getTargetDataSet()}. 402 * 403 * See {@link #getConflicts()} for a map of conflicts after the merge operation. 404 * @param progressMonitor The progress monitor 405 */ 406 public void merge(ProgressMonitor progressMonitor) { 407 merge(progressMonitor, true); 408 } 409 410 /** 411 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in 412 * {@link #getTargetDataSet()}. 413 * 414 * See {@link #getConflicts()} for a map of conflicts after the merge operation. 415 * @param progressMonitor The progress monitor 416 * @param mergeBounds Whether or not to merge the bounds of the new DataSet to 417 * the existing DataSet 418 * @since 15127 419 */ 420 public void merge(ProgressMonitor progressMonitor, boolean mergeBounds) { 421 if (sourceDataSet == null) 422 return; 423 if (progressMonitor != null) { 424 progressMonitor.beginTask(tr("Merging data..."), sourceDataSet.allPrimitives().size()); 425 } 426 targetDataSet.beginUpdate(); 427 try { 428 List<? extends OsmPrimitive> candidates = new ArrayList<>(targetDataSet.getNodes()); 429 for (Node node: sourceDataSet.getNodes()) { 430 mergePrimitive(node, candidates); 431 if (progressMonitor != null) { 432 progressMonitor.worked(1); 433 } 434 } 435 candidates.clear(); 436 candidates = new ArrayList<>(targetDataSet.getWays()); 437 for (Way way: sourceDataSet.getWays()) { 438 mergePrimitive(way, candidates); 439 if (progressMonitor != null) { 440 progressMonitor.worked(1); 441 } 442 } 443 candidates.clear(); 444 candidates = new ArrayList<>(targetDataSet.getRelations()); 445 for (Relation relation: sourceDataSet.getRelations()) { 446 mergePrimitive(relation, candidates); 447 if (progressMonitor != null) { 448 progressMonitor.worked(1); 449 } 450 } 451 candidates.clear(); 452 fixReferences(); 453 454 Area a = targetDataSet.getDataSourceArea(); 455 456 // copy the merged layer's data source info. 457 // only add source rectangles if they are not contained in the layer already. 458 if (mergeBounds) { 459 for (DataSource src : sourceDataSet.getDataSources()) { 460 if (a == null || !a.contains(src.bounds.asRect())) { 461 targetDataSet.addDataSource(src); 462 } 463 } 464 } 465 466 // copy the merged layer's API version 467 if (targetDataSet.getVersion() == null) { 468 targetDataSet.setVersion(sourceDataSet.getVersion()); 469 } 470 471 // copy the merged layer's policies and locked status 472 if (sourceDataSet.getUploadPolicy() != null && (targetDataSet.getUploadPolicy() == null 473 || sourceDataSet.getUploadPolicy().compareTo(targetDataSet.getUploadPolicy()) > 0)) { 474 targetDataSet.setUploadPolicy(sourceDataSet.getUploadPolicy()); 475 } 476 if (sourceDataSet.getDownloadPolicy() != null && (targetDataSet.getDownloadPolicy() == null 477 || sourceDataSet.getDownloadPolicy().compareTo(targetDataSet.getDownloadPolicy()) > 0)) { 478 targetDataSet.setDownloadPolicy(sourceDataSet.getDownloadPolicy()); 479 } 480 if (sourceDataSet.isLocked() && !targetDataSet.isLocked()) { 481 targetDataSet.lock(); 482 } 483 } finally { 484 targetDataSet.endUpdate(); 485 } 486 if (progressMonitor != null) { 487 progressMonitor.finishTask(); 488 } 489 } 490 491 /** 492 * replies my dataset 493 * 494 * @return the own (target) data set 495 */ 496 public DataSet getTargetDataSet() { 497 return targetDataSet; 498 } 499 500 /** 501 * replies the map of conflicts 502 * 503 * @return the map of conflicts 504 */ 505 public ConflictCollection getConflicts() { 506 return conflicts; 507 } 508}