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; 020import org.openstreetmap.josm.tools.JosmRuntimeException; 021 022/** 023 * A dataset merger which takes a target and a source dataset and merges the source data set 024 * onto the target dataset. 025 * 026 */ 027public class DataSetMerger { 028 029 /** the collection of conflicts created during merging */ 030 private final ConflictCollection conflicts; 031 032 /** the target dataset for merging */ 033 private final DataSet targetDataSet; 034 /** the source dataset where primitives are merged from */ 035 private final DataSet sourceDataSet; 036 037 /** 038 * A map of all primitives that got replaced with other primitives. 039 * Key is the PrimitiveId in their dataset, the value is the PrimitiveId in my dataset 040 */ 041 private final Map<PrimitiveId, PrimitiveId> mergedMap; 042 /** a set of primitive ids for which we have to fix references (to nodes and 043 * to relation members) after the first phase of merging 044 */ 045 private final Set<PrimitiveId> objectsWithChildrenToMerge; 046 private final Set<OsmPrimitive> objectsToDelete; 047 048 /** 049 * constructor 050 * 051 * The visitor will merge <code>sourceDataSet</code> onto <code>targetDataSet</code> 052 * 053 * @param targetDataSet dataset with my primitives. Must not be null. 054 * @param sourceDataSet dataset with their primitives. Ignored, if null. 055 * @throws IllegalArgumentException if myDataSet is null 056 */ 057 public DataSetMerger(DataSet targetDataSet, DataSet sourceDataSet) { 058 CheckParameterUtil.ensureParameterNotNull(targetDataSet, "targetDataSet"); 059 this.targetDataSet = targetDataSet; 060 this.sourceDataSet = sourceDataSet; 061 conflicts = new ConflictCollection(); 062 mergedMap = new HashMap<>(); 063 objectsWithChildrenToMerge = new HashSet<>(); 064 objectsToDelete = new HashSet<>(); 065 } 066 067 /** 068 * Merges a primitive onto primitives dataset. 069 * 070 * If other.id != 0 it tries to merge it with an corresponding primitive from 071 * my dataset with the same id. If this is not possible a conflict is remembered 072 * in {@link #conflicts}. 073 * 074 * If other.id == 0 (new primitive) it tries to find a primitive in my dataset with id == 0 which 075 * is semantically equal. If it finds one it merges its technical attributes onto 076 * my primitive. 077 * 078 * @param source the primitive to merge 079 * @param candidates a set of possible candidates for a new primitive 080 */ 081 protected void mergePrimitive(OsmPrimitive source, Collection<? extends OsmPrimitive> candidates) { 082 if (!source.isNew()) { 083 // try to merge onto a matching primitive with the same defined id 084 // 085 if (mergeById(source)) 086 return; 087 } else { 088 // ignore deleted primitives from source 089 if (source.isDeleted()) return; 090 091 // try to merge onto a primitive which has no id assigned 092 // yet but which is equal in its semantic attributes 093 // 094 for (OsmPrimitive target : candidates) { 095 if (!target.isNew() || target.isDeleted()) { 096 continue; 097 } 098 if (target.hasEqualSemanticAttributes(source)) { 099 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId()); 100 // copy the technical attributes from other version 101 target.setVisible(source.isVisible()); 102 target.setUser(source.getUser()); 103 target.setRawTimestamp(source.getRawTimestamp()); 104 target.setModified(source.isModified()); 105 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 106 return; 107 } 108 } 109 } 110 111 // If we get here we didn't find a suitable primitive in 112 // the target dataset. Create a clone and add it to the target dataset. 113 // 114 OsmPrimitive target; 115 switch(source.getType()) { 116 case NODE: target = source.isNew() ? new Node() : new Node(source.getId()); break; 117 case WAY: target = source.isNew() ? new Way() : new Way(source.getId()); break; 118 case RELATION: target = source.isNew() ? new Relation() : new Relation(source.getId()); break; 119 default: throw new AssertionError(); 120 } 121 target.mergeFrom(source); 122 targetDataSet.addPrimitive(target); 123 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId()); 124 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 125 } 126 127 protected OsmPrimitive getMergeTarget(OsmPrimitive mergeSource) { 128 PrimitiveId targetId = mergedMap.get(mergeSource.getPrimitiveId()); 129 if (targetId == null) 130 return null; 131 return targetDataSet.getPrimitiveById(targetId); 132 } 133 134 protected void addConflict(Conflict<?> c) { 135 c.setMergedMap(mergedMap); 136 conflicts.add(c); 137 } 138 139 protected void addConflict(OsmPrimitive my, OsmPrimitive their) { 140 addConflict(new Conflict<>(my, their)); 141 } 142 143 protected void fixIncomplete(Way other) { 144 Way myWay = (Way) getMergeTarget(other); 145 if (myWay == null) 146 throw new JosmRuntimeException(tr("Missing merge target for way with id {0}", other.getUniqueId())); 147 } 148 149 /** 150 * Postprocess the dataset and fix all merged references to point to the actual 151 * data. 152 */ 153 public void fixReferences() { 154 for (Way w : sourceDataSet.getWays()) { 155 if (!conflicts.hasConflictForTheir(w) && objectsWithChildrenToMerge.contains(w.getPrimitiveId())) { 156 mergeNodeList(w); 157 fixIncomplete(w); 158 } 159 } 160 for (Relation r : sourceDataSet.getRelations()) { 161 if (!conflicts.hasConflictForTheir(r) && objectsWithChildrenToMerge.contains(r.getPrimitiveId())) { 162 mergeRelationMembers(r); 163 } 164 } 165 166 deleteMarkedObjects(); 167 } 168 169 /** 170 * Deleted objects in objectsToDelete set and create conflicts for objects that cannot 171 * be deleted because they're referenced in the target dataset. 172 */ 173 protected void deleteMarkedObjects() { 174 boolean flag; 175 do { 176 flag = false; 177 for (Iterator<OsmPrimitive> it = objectsToDelete.iterator(); it.hasNext();) { 178 OsmPrimitive target = it.next(); 179 OsmPrimitive source = sourceDataSet.getPrimitiveById(target.getPrimitiveId()); 180 if (source == null) 181 throw new JosmRuntimeException( 182 tr("Object of type {0} with id {1} was marked to be deleted, but it''s missing in the source dataset", 183 target.getType(), target.getUniqueId())); 184 185 List<OsmPrimitive> referrers = target.getReferrers(); 186 if (referrers.isEmpty()) { 187 resetPrimitive(target); 188 target.mergeFrom(source); 189 target.setDeleted(true); 190 it.remove(); 191 flag = true; 192 } else { 193 for (OsmPrimitive referrer : referrers) { 194 // If one of object referrers isn't going to be deleted, 195 // add a conflict and don't delete the object 196 if (!objectsToDelete.contains(referrer)) { 197 addConflict(target, source); 198 it.remove(); 199 flag = true; 200 break; 201 } 202 } 203 } 204 205 } 206 } while (flag); 207 208 if (!objectsToDelete.isEmpty()) { 209 // There are some more objects rest in the objectsToDelete set 210 // This can be because of cross-referenced relations. 211 for (OsmPrimitive osm: objectsToDelete) { 212 resetPrimitive(osm); 213 } 214 for (OsmPrimitive osm: objectsToDelete) { 215 osm.setDeleted(true); 216 osm.mergeFrom(sourceDataSet.getPrimitiveById(osm.getPrimitiveId())); 217 } 218 } 219 } 220 221 private static void resetPrimitive(OsmPrimitive osm) { 222 if (osm instanceof Way) { 223 ((Way) osm).setNodes(null); 224 } else if (osm instanceof Relation) { 225 ((Relation) osm).setMembers(null); 226 } 227 } 228 229 /** 230 * Merges the node list of a source way onto its target way. 231 * 232 * @param source the source way 233 * @throws IllegalStateException if no target way can be found for the source way 234 * @throws IllegalStateException if there isn't a target node for one of the nodes in the source way 235 * 236 */ 237 private void mergeNodeList(Way source) { 238 Way target = (Way) getMergeTarget(source); 239 if (target == null) 240 throw new IllegalStateException(tr("Missing merge target for way with id {0}", source.getUniqueId())); 241 242 List<Node> newNodes = new ArrayList<>(source.getNodesCount()); 243 for (Node sourceNode : source.getNodes()) { 244 Node targetNode = (Node) getMergeTarget(sourceNode); 245 if (targetNode != null) { 246 newNodes.add(targetNode); 247 if (targetNode.isDeleted() && !conflicts.hasConflictForMy(targetNode)) { 248 addConflict(new Conflict<OsmPrimitive>(targetNode, sourceNode, true)); 249 targetNode.setDeleted(false); 250 } 251 } else 252 throw new IllegalStateException(tr("Missing merge target for node with id {0}", sourceNode.getUniqueId())); 253 } 254 target.setNodes(newNodes); 255 } 256 257 /** 258 * Merges the relation members of a source relation onto the corresponding target relation. 259 * @param source the source relation 260 * @throws IllegalStateException if there is no corresponding target relation 261 * @throws IllegalStateException if there isn't a corresponding target object for one of the relation 262 * members in source 263 */ 264 private void mergeRelationMembers(Relation source) { 265 Relation target = (Relation) getMergeTarget(source); 266 if (target == null) 267 throw new IllegalStateException(tr("Missing merge target for relation with id {0}", source.getUniqueId())); 268 List<RelationMember> newMembers = new LinkedList<>(); 269 for (RelationMember sourceMember : source.getMembers()) { 270 OsmPrimitive targetMember = getMergeTarget(sourceMember.getMember()); 271 if (targetMember == null) 272 throw new IllegalStateException(tr("Missing merge target of type {0} with id {1}", 273 sourceMember.getType(), sourceMember.getUniqueId())); 274 RelationMember newMember = new RelationMember(sourceMember.getRole(), targetMember); 275 newMembers.add(newMember); 276 if (targetMember.isDeleted() && !conflicts.hasConflictForMy(targetMember)) { 277 addConflict(new Conflict<>(targetMember, sourceMember.getMember(), true)); 278 targetMember.setDeleted(false); 279 } 280 } 281 target.setMembers(newMembers); 282 } 283 284 /** 285 * Tries to merge a primitive <code>source</code> into an existing primitive with the same id. 286 * 287 * @param source the source primitive which is to be merged into a target primitive 288 * @return true, if this method was able to merge <code>source</code> into a target object; false, otherwise 289 */ 290 private boolean mergeById(OsmPrimitive source) { 291 OsmPrimitive target = targetDataSet.getPrimitiveById(source.getId(), source.getType()); 292 // merge other into an existing primitive with the same id, if possible 293 // 294 if (target == null) 295 return false; 296 // found a corresponding target, remember it 297 mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId()); 298 299 if (target.getVersion() > source.getVersion()) 300 // target.version > source.version => keep target version 301 return true; 302 303 if (target.isIncomplete() && !source.isIncomplete()) { 304 // target is incomplete, source completes it 305 // => merge source into target 306 // 307 target.mergeFrom(source); 308 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 309 } else if (!target.isIncomplete() && source.isIncomplete()) { 310 // target is complete and source is incomplete 311 // => keep target, it has more information already 312 // 313 } else if (target.isIncomplete() && source.isIncomplete()) { 314 // target and source are incomplete. Doesn't matter which one to 315 // take. We take target. 316 // 317 } else if (!target.isModified() && !source.isModified() && target.isVisible() != source.isVisible() 318 && target.getVersion() == source.getVersion()) 319 // Same version, but different "visible" attribute and neither of them are modified. 320 // It indicates a serious problem in datasets. 321 // For example, datasets can be fetched from different OSM servers or badly hand-modified. 322 // We shouldn't merge that datasets. 323 throw new DataIntegrityProblemException(tr("Conflict in ''visible'' attribute for object of type {0} with id {1}", 324 target.getType(), target.getId())); 325 else if (target.isDeleted() && !source.isDeleted() && target.getVersion() == source.getVersion()) { 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 has a referrer that is not in the target dataset there is a conflict 329 // If target dataset refers to the deleted primitive, conflict will be added in fixReferences method 330 for (OsmPrimitive referrer: source.getReferrers()) { 331 if (targetDataSet.getPrimitiveById(referrer.getPrimitiveId()) == null) { 332 addConflict(new Conflict<>(target, source, true)); 333 target.setDeleted(false); 334 break; 335 } 336 } 337 } else if (!target.isModified() && source.isDeleted()) { 338 // target not modified. We can assume that source is the most recent version, 339 // so mark it to be deleted. 340 // 341 objectsToDelete.add(target); 342 } else if (!target.isModified() && source.isModified()) { 343 // target not modified. We can assume that source is the most recent version. 344 // clone it into target. 345 target.mergeFrom(source); 346 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 347 } else if (!target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) { 348 // both not modified. Merge nevertheless. 349 // This helps when updating "empty" relations, see #4295 350 target.mergeFrom(source); 351 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 352 } else if (!target.isModified() && !source.isModified() && target.getVersion() < source.getVersion()) { 353 // my not modified but other is newer. clone other onto mine. 354 // 355 target.mergeFrom(source); 356 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 357 } else if (target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) { 358 // target is same as source but target is modified 359 // => keep target and reset modified flag if target and source are semantically equal 360 if (target.hasEqualSemanticAttributes(source, false)) { 361 target.setModified(false); 362 } 363 } else if (source.isDeleted() != target.isDeleted()) { 364 // target is modified and deleted state differs. 365 // this have to be resolved manually. 366 // 367 addConflict(target, source); 368 } else if (!target.hasEqualSemanticAttributes(source)) { 369 // target is modified and is not semantically equal with source. Can't automatically 370 // resolve the differences 371 // => create a conflict 372 addConflict(target, source); 373 } else { 374 // clone from other. mergeFrom will mainly copy 375 // technical attributes like timestamp or user information. Semantic 376 // attributes should already be equal if we get here. 377 // 378 target.mergeFrom(source); 379 objectsWithChildrenToMerge.add(source.getPrimitiveId()); 380 } 381 return true; 382 } 383 384 /** 385 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in 386 * {@link #getTargetDataSet()}. 387 * 388 * See {@link #getConflicts()} for a map of conflicts after the merge operation. 389 */ 390 public void merge() { 391 merge(null); 392 } 393 394 /** 395 * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in 396 * {@link #getTargetDataSet()}. 397 * 398 * See {@link #getConflicts()} for a map of conflicts after the merge operation. 399 * @param progressMonitor The progress monitor 400 */ 401 public void merge(ProgressMonitor progressMonitor) { 402 if (sourceDataSet == null) 403 return; 404 if (progressMonitor != null) { 405 progressMonitor.beginTask(tr("Merging data..."), sourceDataSet.allPrimitives().size()); 406 } 407 targetDataSet.beginUpdate(); 408 try { 409 List<? extends OsmPrimitive> candidates = new ArrayList<>(targetDataSet.getNodes()); 410 for (Node node: sourceDataSet.getNodes()) { 411 mergePrimitive(node, candidates); 412 if (progressMonitor != null) { 413 progressMonitor.worked(1); 414 } 415 } 416 candidates.clear(); 417 candidates = new ArrayList<>(targetDataSet.getWays()); 418 for (Way way: sourceDataSet.getWays()) { 419 mergePrimitive(way, candidates); 420 if (progressMonitor != null) { 421 progressMonitor.worked(1); 422 } 423 } 424 candidates.clear(); 425 candidates = new ArrayList<>(targetDataSet.getRelations()); 426 for (Relation relation: sourceDataSet.getRelations()) { 427 mergePrimitive(relation, candidates); 428 if (progressMonitor != null) { 429 progressMonitor.worked(1); 430 } 431 } 432 candidates.clear(); 433 fixReferences(); 434 } finally { 435 targetDataSet.endUpdate(); 436 } 437 if (progressMonitor != null) { 438 progressMonitor.finishTask(); 439 } 440 } 441 442 /** 443 * replies my dataset 444 * 445 * @return the own (target) data set 446 */ 447 public DataSet getTargetDataSet() { 448 return targetDataSet; 449 } 450 451 /** 452 * replies the map of conflicts 453 * 454 * @return the map of conflicts 455 */ 456 public ConflictCollection getConflicts() { 457 return conflicts; 458 } 459}