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 IPrimitive.resetPrimitiveChildren(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 IPrimitive.resetPrimitiveChildren(osm); 215 } 216 for (OsmPrimitive osm: objectsToDelete) { 217 osm.setDeleted(true); 218 osm.mergeFrom(sourceDataSet.getPrimitiveById(osm.getPrimitiveId())); 219 } 220 } 221 } 222 223 /** 224 * Merges the node list of a source way onto its target way. 225 * 226 * @param source the source way 227 * @throws IllegalStateException if no target way can be found for the source way 228 * @throws IllegalStateException if there isn't a target node for one of the nodes in the source way 229 * 230 */ 231 private void mergeNodeList(Way source) { 232 Way target = (Way) getMergeTarget(source); 233 if (target == null) 234 throw new IllegalStateException(tr("Missing merge target for way with id {0}", source.getUniqueId())); 235 236 List<Node> newNodes = new ArrayList<>(source.getNodesCount()); 237 for (Node sourceNode : source.getNodes()) { 238 Node targetNode = (Node) getMergeTarget(sourceNode); 239 if (targetNode != null) { 240 newNodes.add(targetNode); 241 if (targetNode.isDeleted() && !conflicts.hasConflictForMy(targetNode)) { 242 addConflict(new Conflict<OsmPrimitive>(targetNode, sourceNode, true)); 243 targetNode.setDeleted(false); 244 } 245 } else 246 throw new IllegalStateException(tr("Missing merge target for node with id {0}", sourceNode.getUniqueId())); 247 } 248 target.setNodes(newNodes); 249 } 250 251 /** 252 * Merges the relation members of a source relation onto the corresponding target relation. 253 * @param source the source relation 254 * @throws IllegalStateException if there is no corresponding target relation 255 * @throws IllegalStateException if there isn't a corresponding target object for one of the relation 256 * members in source 257 */ 258 private void mergeRelationMembers(Relation source) { 259 Relation target = (Relation) getMergeTarget(source); 260 if (target == null) 261 throw new IllegalStateException(tr("Missing merge target for relation with id {0}", source.getUniqueId())); 262 List<RelationMember> newMembers = new LinkedList<>(); 263 for (RelationMember sourceMember : source.getMembers()) { 264 OsmPrimitive targetMember = getMergeTarget(sourceMember.getMember()); 265 if (targetMember == null) 266 throw new IllegalStateException(tr("Missing merge target of type {0} with id {1}", 267 sourceMember.getType(), sourceMember.getUniqueId())); 268 newMembers.add(new RelationMember(sourceMember.getRole(), targetMember)); 269 if (targetMember.isDeleted() && !conflicts.hasConflictForMy(targetMember)) { 270 addConflict(new Conflict<>(targetMember, sourceMember.getMember(), true)); 271 targetMember.setDeleted(false); 272 } 273 } 274 target.setMembers(newMembers); 275 } 276 277 /** 278 * Tries to merge a primitive <code>source</code> into an existing primitive with the same id. 279 * 280 * @param source the source primitive which is to be merged into a target primitive 281 * @return true, if this method was able to merge <code>source</code> into a target object; false, otherwise 282 */ 283 private boolean mergeById(OsmPrimitive source) { 284 OsmPrimitive target = targetDataSet.getPrimitiveById(source.getId(), source.getType()); 285 // merge other into an existing primitive with the same id, if possible 286 // 287 if (target == null) 288 return false; 289 // found a corresponding target, remember it 290 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId()); 291 292 if (target.getVersion() > source.getVersion()) 293 // target.version > source.version => keep target version 294 return true; 295 296 boolean mergeFromSource = false; 297 boolean haveSameVersion = target.getVersion() == source.getVersion(); 298 299 if (haveSameVersion && !target.isModified() && !source.isModified() 300 && target.isVisible() != source.isVisible()) { 301 // Same version, but different "visible" attribute and neither of them are modified. 302 // It indicates a serious problem in datasets. 303 // For example, datasets can be fetched from different OSM servers or badly hand-modified. 304 // We shouldn't merge that datasets. 305 throw new DataIntegrityProblemException(tr("Conflict in ''visible'' attribute for object of type {0} with id {1}", 306 target.getType(), target.getId())); 307 } 308 309 if (!target.isModified() && source.isDeleted()) { 310 // target not modified and source is deleted 311 // So mark it to be deleted. See #20091 312 // 313 objectsToDelete.add(target); 314 } else if (source.isIncomplete()) { 315 // source is incomplete. Nothing to do. 316 // 317 } else if (target.isIncomplete()) { 318 // target is incomplete, source completes it 319 // => merge source into target 320 // 321 mergeFromSource = true; 322 } else if (target.isDeleted() && source.isDeleted() && !haveSameVersion) { 323 // both deleted. Source is newer. Take source. See #19783 324 mergeFromSource = true; 325 } else if (target.isDeleted() && !source.isDeleted() && haveSameVersion) { 326 // same version, but target is deleted. Assume target takes precedence 327 // otherwise too many conflicts when refreshing from the server 328 // but, if source is modified, there is a conflict 329 if (source.isModified()) { 330 addConflict(new Conflict<>(target, source, true)); 331 } 332 // or, if source has a referrer that is not in the target dataset there is a conflict 333 // If target dataset refers to the deleted primitive, conflict will be added in fixReferences method 334 for (OsmPrimitive referrer: source.getReferrers()) { 335 if (targetDataSet.getPrimitiveById(referrer.getPrimitiveId()) == null) { 336 addConflict(new Conflict<>(target, source, true)); 337 target.setDeleted(false); 338 break; 339 } 340 } 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 mergeFromSource = true; 345 } else if (!target.isModified() && !source.isModified()) { 346 // both not modified. Merge nevertheless, even if versions are the same 347 // This helps when updating "empty" relations, see #4295 348 mergeFromSource = true; 349 } else if (target.isModified() && !source.isModified() && haveSameVersion) { 350 // target is same as source but target is modified 351 // => keep target and reset modified flag if target and source are semantically equal 352 if (target.hasEqualSemanticAttributes(source, false)) { 353 target.setModified(false); 354 } 355 } else if (source.isDeleted() != target.isDeleted()) { 356 // target is modified and deleted state differs. 357 // this has to be resolved manually. 358 // 359 addConflict(target, source); 360 } else if (!target.hasEqualSemanticAttributes(source)) { 361 // target is modified and is not semantically equal with source. Can't automatically 362 // resolve the differences 363 // => create a conflict 364 addConflict(target, source); 365 } else { 366 // clone from other. mergeFrom will mainly copy 367 // technical attributes like timestamp or user information. Semantic 368 // attributes should already be equal if we get here. 369 // 370 mergeFromSource = true; 371 } 372 if (mergeFromSource) { 373 target.mergeFrom(source); 374 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 375 } 376 return true; 377 } 378 379 /** 380 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in 381 * {@link #getTargetDataSet()}. 382 * 383 * See {@link #getConflicts()} for a map of conflicts after the merge operation. 384 */ 385 public void merge() { 386 merge(null); 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 * @param progressMonitor The progress monitor 395 */ 396 public void merge(ProgressMonitor progressMonitor) { 397 merge(progressMonitor, true); 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 * @param mergeBounds Whether or not to merge the bounds of the new DataSet to 407 * the existing DataSet 408 * @since 15127 409 */ 410 public void merge(ProgressMonitor progressMonitor, boolean mergeBounds) { 411 if (sourceDataSet == null) 412 return; 413 if (progressMonitor != null) { 414 progressMonitor.beginTask(tr("Merging data..."), sourceDataSet.allPrimitives().size()); 415 } 416 targetDataSet.update(() -> { 417 List<? extends OsmPrimitive> candidates = null; 418 for (Node node: sourceDataSet.getNodes()) { 419 // lazy initialisation to improve performance, see #19898 420 if (candidates == null) { 421 candidates = new ArrayList<>(targetDataSet.getNodes()); 422 } 423 mergePrimitive(node, candidates); 424 if (progressMonitor != null) { 425 progressMonitor.worked(1); 426 } 427 } 428 candidates = null; 429 for (Way way: sourceDataSet.getWays()) { 430 // lazy initialisation to improve performance 431 if (candidates == null) { 432 candidates = new ArrayList<>(targetDataSet.getWays()); 433 } 434 mergePrimitive(way, candidates); 435 if (progressMonitor != null) { 436 progressMonitor.worked(1); 437 } 438 } 439 candidates = null; 440 for (Relation relation: sourceDataSet.getRelations()) { 441 // lazy initialisation to improve performance 442 if (candidates == null) { 443 candidates = new ArrayList<>(targetDataSet.getRelations()); 444 } 445 mergePrimitive(relation, candidates); 446 if (progressMonitor != null) { 447 progressMonitor.worked(1); 448 } 449 } 450 candidates = null; 451 fixReferences(); 452 453 Area a = targetDataSet.getDataSourceArea(); 454 455 // copy the merged layer's data source info. 456 // only add source rectangles if they are not contained in the layer already. 457 if (mergeBounds) { 458 for (DataSource src : sourceDataSet.getDataSources()) { 459 if (a == null || !a.contains(src.bounds.asRect())) { 460 targetDataSet.addDataSource(src); 461 } 462 } 463 } 464 465 // copy the merged layer's API version 466 if (targetDataSet.getVersion() == null) { 467 targetDataSet.setVersion(sourceDataSet.getVersion()); 468 } 469 470 // copy the merged layer's policies and locked status 471 if (sourceDataSet.getUploadPolicy() != null && (targetDataSet.getUploadPolicy() == null 472 || sourceDataSet.getUploadPolicy().compareTo(targetDataSet.getUploadPolicy()) > 0)) { 473 targetDataSet.setUploadPolicy(sourceDataSet.getUploadPolicy()); 474 } 475 if (sourceDataSet.getDownloadPolicy() != null && (targetDataSet.getDownloadPolicy() == null 476 || sourceDataSet.getDownloadPolicy().compareTo(targetDataSet.getDownloadPolicy()) > 0)) { 477 targetDataSet.setDownloadPolicy(sourceDataSet.getDownloadPolicy()); 478 } 479 if (sourceDataSet.isLocked() && !targetDataSet.isLocked()) { 480 targetDataSet.lock(); 481 } 482 }); 483 if (progressMonitor != null) { 484 progressMonitor.finishTask(); 485 } 486 } 487 488 /** 489 * replies my dataset 490 * 491 * @return the own (target) data set 492 */ 493 public DataSet getTargetDataSet() { 494 return targetDataSet; 495 } 496 497 /** 498 * replies the map of conflicts 499 * 500 * @return the map of conflicts 501 */ 502 public ConflictCollection getConflicts() { 503 return conflicts; 504 } 505}