1 | // License: GPL. For details, see LICENSE file.
|
---|
2 | package org.openstreetmap.josm.data.osm;
|
---|
3 |
|
---|
4 | import static org.openstreetmap.josm.tools.I18n.tr;
|
---|
5 |
|
---|
6 | import java.util.ArrayList;
|
---|
7 | import java.util.Collection;
|
---|
8 | import java.util.HashMap;
|
---|
9 | import java.util.HashSet;
|
---|
10 | import java.util.Iterator;
|
---|
11 | import java.util.LinkedList;
|
---|
12 | import java.util.List;
|
---|
13 | import java.util.Map;
|
---|
14 | import java.util.Set;
|
---|
15 |
|
---|
16 | import org.openstreetmap.josm.data.conflict.Conflict;
|
---|
17 | import org.openstreetmap.josm.data.conflict.ConflictCollection;
|
---|
18 | import org.openstreetmap.josm.gui.progress.ProgressMonitor;
|
---|
19 | import org.openstreetmap.josm.tools.CheckParameterUtil;
|
---|
20 |
|
---|
21 | /**
|
---|
22 | * A dataset merger which takes a target and a source dataset and merges the source data set
|
---|
23 | * onto the target dataset.
|
---|
24 | *
|
---|
25 | */
|
---|
26 | public class DataSetMerger {
|
---|
27 |
|
---|
28 | /** the collection of conflicts created during merging */
|
---|
29 | private final ConflictCollection conflicts;
|
---|
30 |
|
---|
31 | /** the target dataset for merging */
|
---|
32 | private final DataSet targetDataSet;
|
---|
33 | /** the source dataset where primitives are merged from */
|
---|
34 | private final DataSet sourceDataSet;
|
---|
35 |
|
---|
36 | /**
|
---|
37 | * A map of all primitives that got replaced with other primitives.
|
---|
38 | * Key is the PrimitiveId in their dataset, the value is the PrimitiveId in my dataset
|
---|
39 | */
|
---|
40 | private final Map<PrimitiveId, PrimitiveId> mergedMap;
|
---|
41 | /** a set of primitive ids for which we have to fix references (to nodes and
|
---|
42 | * to relation members) after the first phase of merging
|
---|
43 | */
|
---|
44 | private final Set<PrimitiveId> objectsWithChildrenToMerge;
|
---|
45 | private final Set<OsmPrimitive> objectsToDelete;
|
---|
46 |
|
---|
47 | /**
|
---|
48 | * constructor
|
---|
49 | *
|
---|
50 | * The visitor will merge <code>theirDataSet</code> onto <code>myDataSet</code>
|
---|
51 | *
|
---|
52 | * @param targetDataSet dataset with my primitives. Must not be null.
|
---|
53 | * @param sourceDataSet dataset with their primitives. Ignored, if null.
|
---|
54 | * @throws IllegalArgumentException thrown if myDataSet is null
|
---|
55 | */
|
---|
56 | public DataSetMerger(DataSet targetDataSet, DataSet sourceDataSet) throws IllegalArgumentException {
|
---|
57 | CheckParameterUtil.ensureParameterNotNull(targetDataSet, "targetDataSet");
|
---|
58 | this.targetDataSet = targetDataSet;
|
---|
59 | this.sourceDataSet = sourceDataSet;
|
---|
60 | conflicts = new ConflictCollection();
|
---|
61 | mergedMap = new HashMap<PrimitiveId, PrimitiveId>();
|
---|
62 | objectsWithChildrenToMerge = new HashSet<PrimitiveId>();
|
---|
63 | objectsToDelete = new HashSet<OsmPrimitive>();
|
---|
64 | }
|
---|
65 |
|
---|
66 | /**
|
---|
67 | * Merges a primitive <code>other</code> of type <P> onto my primitives.
|
---|
68 | *
|
---|
69 | * If other.id != 0 it tries to merge it with an corresponding primitive from
|
---|
70 | * my dataset with the same id. If this is not possible a conflict is remembered
|
---|
71 | * in {@see #conflicts}.
|
---|
72 | *
|
---|
73 | * If other.id == 0 it tries to find a primitive in my dataset with id == 0 which
|
---|
74 | * is semantically equal. If it finds one it merges its technical attributes onto
|
---|
75 | * my primitive.
|
---|
76 | *
|
---|
77 | * @param <P> the type of the other primitive
|
---|
78 | * @param source the other primitive
|
---|
79 | */
|
---|
80 | protected void mergePrimitive(OsmPrimitive source, Collection<? extends OsmPrimitive> candidates) {
|
---|
81 | if (!source.isNew() ) {
|
---|
82 | // try to merge onto a matching primitive with the same
|
---|
83 | // defined id
|
---|
84 | //
|
---|
85 | if (mergeById(source))
|
---|
86 | return;
|
---|
87 | //if (!source.isVisible())
|
---|
88 | // ignore it
|
---|
89 | // return;
|
---|
90 | } else {
|
---|
91 | // ignore deleted primitives from source
|
---|
92 | if (source.isDeleted()) return;
|
---|
93 |
|
---|
94 | // try to merge onto a primitive which has no id assigned
|
---|
95 | // yet but which is equal in its semantic attributes
|
---|
96 | //
|
---|
97 | for (OsmPrimitive target : candidates) {
|
---|
98 | if (!target.isNew() || target.isDeleted()) {
|
---|
99 | continue;
|
---|
100 | }
|
---|
101 | if (target.hasEqualSemanticAttributes(source)) {
|
---|
102 | mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId());
|
---|
103 | // copy the technical attributes from other
|
---|
104 | // version
|
---|
105 | target.setVisible(source.isVisible());
|
---|
106 | target.setUser(source.getUser());
|
---|
107 | target.setTimestamp(source.getTimestamp());
|
---|
108 | target.setModified(source.isModified());
|
---|
109 | objectsWithChildrenToMerge.add(source.getPrimitiveId());
|
---|
110 | return;
|
---|
111 | }
|
---|
112 | }
|
---|
113 | }
|
---|
114 |
|
---|
115 | // If we get here we didn't find a suitable primitive in
|
---|
116 | // the target dataset. Create a clone and add it to the target dataset.
|
---|
117 | //
|
---|
118 | OsmPrimitive target = null;
|
---|
119 | switch(source.getType()) {
|
---|
120 | case NODE: target = source.isNew() ? new Node() : new Node(source.getId()); break;
|
---|
121 | case WAY: target = source.isNew() ? new Way() : new Way(source.getId()); break;
|
---|
122 | case RELATION: target = source.isNew() ? new Relation() : new Relation(source.getId()); break;
|
---|
123 | default: throw new AssertionError();
|
---|
124 | }
|
---|
125 | target.mergeFrom(source);
|
---|
126 | targetDataSet.addPrimitive(target);
|
---|
127 | mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId());
|
---|
128 | objectsWithChildrenToMerge.add(source.getPrimitiveId());
|
---|
129 | }
|
---|
130 |
|
---|
131 | protected OsmPrimitive getMergeTarget(OsmPrimitive mergeSource) throws IllegalStateException {
|
---|
132 | PrimitiveId targetId = mergedMap.get(mergeSource.getPrimitiveId());
|
---|
133 | if (targetId == null)
|
---|
134 | return null;
|
---|
135 | return targetDataSet.getPrimitiveById(targetId);
|
---|
136 | }
|
---|
137 |
|
---|
138 | protected void fixIncomplete(Way other) {
|
---|
139 | Way myWay = (Way)getMergeTarget(other);
|
---|
140 | if (myWay == null)
|
---|
141 | throw new RuntimeException(tr("Missing merge target for way with id {0}", other.getUniqueId()));
|
---|
142 | }
|
---|
143 |
|
---|
144 | /**
|
---|
145 | * Postprocess the dataset and fix all merged references to point to the actual
|
---|
146 | * data.
|
---|
147 | */
|
---|
148 | public void fixReferences() {
|
---|
149 | for (Way w : sourceDataSet.getWays()) {
|
---|
150 | if (!conflicts.hasConflictForTheir(w) && objectsWithChildrenToMerge.contains(w.getPrimitiveId())) {
|
---|
151 | mergeNodeList(w);
|
---|
152 | fixIncomplete(w);
|
---|
153 | }
|
---|
154 | }
|
---|
155 | for (Relation r : sourceDataSet.getRelations()) {
|
---|
156 | if (!conflicts.hasConflictForTheir(r) && objectsWithChildrenToMerge.contains(r.getPrimitiveId())) {
|
---|
157 | mergeRelationMembers(r);
|
---|
158 | }
|
---|
159 | }
|
---|
160 |
|
---|
161 | deleteMarkedObjects();
|
---|
162 | }
|
---|
163 |
|
---|
164 | /**
|
---|
165 | * Deleted objects in objectsToDelete set and create conflicts for objects that cannot
|
---|
166 | * be deleted because they're referenced in the target dataset.
|
---|
167 | */
|
---|
168 | protected void deleteMarkedObjects() {
|
---|
169 | boolean flag;
|
---|
170 | do {
|
---|
171 | flag = false;
|
---|
172 | for (Iterator<OsmPrimitive> it = objectsToDelete.iterator();it.hasNext();) {
|
---|
173 | OsmPrimitive target = it.next();
|
---|
174 | OsmPrimitive source = sourceDataSet.getPrimitiveById(target.getPrimitiveId());
|
---|
175 | if (source == null)
|
---|
176 | throw new RuntimeException(tr("Object of type {0} with id {1} was marked to be deleted, but it''s missing in the source dataset",
|
---|
177 | target.getType(), target.getUniqueId()));
|
---|
178 |
|
---|
179 | List<OsmPrimitive> referrers = target.getReferrers();
|
---|
180 | if (referrers.isEmpty()) {
|
---|
181 | target.setDeleted(true);
|
---|
182 | target.mergeFrom(source);
|
---|
183 | it.remove();
|
---|
184 | flag = true;
|
---|
185 | } else {
|
---|
186 | for (OsmPrimitive referrer : referrers) {
|
---|
187 | // If one of object referrers isn't going to be deleted,
|
---|
188 | // add a conflict and don't delete the object
|
---|
189 | if (!objectsToDelete.contains(referrer)) {
|
---|
190 | conflicts.add(target, source);
|
---|
191 | it.remove();
|
---|
192 | flag = true;
|
---|
193 | break;
|
---|
194 | }
|
---|
195 | }
|
---|
196 | }
|
---|
197 |
|
---|
198 | }
|
---|
199 | } while (flag);
|
---|
200 |
|
---|
201 | if (!objectsToDelete.isEmpty()) {
|
---|
202 | // There are some more objects rest in the objectsToDelete set
|
---|
203 | // This can be because of cross-referenced relations.
|
---|
204 | for (OsmPrimitive osm: objectsToDelete) {
|
---|
205 | if (osm instanceof Way) {
|
---|
206 | ((Way) osm).setNodes(null);
|
---|
207 | } else if (osm instanceof Relation) {
|
---|
208 | ((Relation) osm).setMembers(null);
|
---|
209 | }
|
---|
210 | }
|
---|
211 | for (OsmPrimitive osm: objectsToDelete) {
|
---|
212 | osm.setDeleted(true);
|
---|
213 | osm.mergeFrom(sourceDataSet.getPrimitiveById(osm.getPrimitiveId()));
|
---|
214 | }
|
---|
215 | }
|
---|
216 | }
|
---|
217 |
|
---|
218 | /**
|
---|
219 | * Merges the node list of a source way onto its target way.
|
---|
220 | *
|
---|
221 | * @param source the source way
|
---|
222 | * @throws IllegalStateException thrown if no target way can be found for the source way
|
---|
223 | * @throws IllegalStateException thrown if there isn't a target node for one of the nodes in the source way
|
---|
224 | *
|
---|
225 | */
|
---|
226 | private void mergeNodeList(Way source) throws IllegalStateException {
|
---|
227 | Way target = (Way)getMergeTarget(source);
|
---|
228 | if (target == null)
|
---|
229 | throw new IllegalStateException(tr("Missing merge target for way with id {0}", source.getUniqueId()));
|
---|
230 |
|
---|
231 | List<Node> newNodes = new ArrayList<Node>(source.getNodesCount());
|
---|
232 | for (Node sourceNode : source.getNodes()) {
|
---|
233 | Node targetNode = (Node)getMergeTarget(sourceNode);
|
---|
234 | if (targetNode != null) {
|
---|
235 | newNodes.add(targetNode);
|
---|
236 | if (targetNode.isDeleted() && !conflicts.hasConflictForMy(targetNode)) {
|
---|
237 | conflicts.add(new Conflict<OsmPrimitive>(targetNode, sourceNode, true));
|
---|
238 | targetNode.setDeleted(false);
|
---|
239 | }
|
---|
240 | } else
|
---|
241 | throw new IllegalStateException(tr("Missing merge target for node with id {0}", sourceNode.getUniqueId()));
|
---|
242 | }
|
---|
243 | target.setNodes(newNodes);
|
---|
244 | }
|
---|
245 |
|
---|
246 | /**
|
---|
247 | * Merges the relation members of a source relation onto the corresponding target relation.
|
---|
248 | * @param source the source relation
|
---|
249 | * @throws IllegalStateException thrown if there is no corresponding target relation
|
---|
250 | * @throws IllegalStateException thrown if there isn't a corresponding target object for one of the relation
|
---|
251 | * members in source
|
---|
252 | */
|
---|
253 | private void mergeRelationMembers(Relation source) throws IllegalStateException {
|
---|
254 | Relation target = (Relation) getMergeTarget(source);
|
---|
255 | if (target == null)
|
---|
256 | throw new IllegalStateException(tr("Missing merge target for relation with id {0}", source.getUniqueId()));
|
---|
257 | LinkedList<RelationMember> newMembers = new LinkedList<RelationMember>();
|
---|
258 | for (RelationMember sourceMember : source.getMembers()) {
|
---|
259 | OsmPrimitive targetMember = getMergeTarget(sourceMember.getMember());
|
---|
260 | if (targetMember == null)
|
---|
261 | throw new IllegalStateException(tr("Missing merge target of type {0} with id {1}", sourceMember.getType(), sourceMember.getUniqueId()));
|
---|
262 | RelationMember newMember = new RelationMember(sourceMember.getRole(), targetMember);
|
---|
263 | newMembers.add(newMember);
|
---|
264 | if (targetMember.isDeleted() && !conflicts.hasConflictForMy(targetMember)) {
|
---|
265 | conflicts.add(new Conflict<OsmPrimitive>(targetMember, sourceMember.getMember(), true));
|
---|
266 | targetMember.setDeleted(false);
|
---|
267 | }
|
---|
268 | }
|
---|
269 | target.setMembers(newMembers);
|
---|
270 | }
|
---|
271 |
|
---|
272 | /**
|
---|
273 | * Tries to merge a primitive <code>source</code> into an existing primitive with the same id.
|
---|
274 | *
|
---|
275 | * @param source the source primitive which is to be merged into a target primitive
|
---|
276 | * @return true, if this method was able to merge <code>source</code> into a target object; false, otherwise
|
---|
277 | */
|
---|
278 | private boolean mergeById(OsmPrimitive source) {
|
---|
279 | OsmPrimitive target = targetDataSet.getPrimitiveById(source.getId(), source.getType());
|
---|
280 | // merge other into an existing primitive with the same id, if possible
|
---|
281 | //
|
---|
282 | if (target == null)
|
---|
283 | return false;
|
---|
284 | // found a corresponding target, remember it
|
---|
285 | mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId());
|
---|
286 |
|
---|
287 | if (target.getVersion() > source.getVersion())
|
---|
288 | // target.version > source.version => keep target version
|
---|
289 | return true;
|
---|
290 |
|
---|
291 | if (target.isIncomplete() && !source.isIncomplete()) {
|
---|
292 | // target is incomplete, source completes it
|
---|
293 | // => merge source into target
|
---|
294 | //
|
---|
295 | target.mergeFrom(source);
|
---|
296 | objectsWithChildrenToMerge.add(source.getPrimitiveId());
|
---|
297 | } else if (!target.isIncomplete() && source.isIncomplete()) {
|
---|
298 | // target is complete and source is incomplete
|
---|
299 | // => keep target, it has more information already
|
---|
300 | //
|
---|
301 | } else if (target.isIncomplete() && source.isIncomplete()) {
|
---|
302 | // target and source are incomplete. Doesn't matter which one to
|
---|
303 | // take. We take target.
|
---|
304 | //
|
---|
305 | } else if (!target.isModified() && !source.isModified() && target.isVisible() != source.isVisible() && target.getVersion() == source.getVersion())
|
---|
306 | // Same version, but different "visible" attribute and neither of them are modified.
|
---|
307 | // It indicates a serious problem in datasets.
|
---|
308 | // For example, datasets can be fetched from different OSM servers or badly hand-modified.
|
---|
309 | // We shouldn't merge that datasets.
|
---|
310 | throw new DataIntegrityProblemException(tr("Conflict in ''visible'' attribute for object of type {0} with id {1}",
|
---|
311 | target.getType(), target.getId()));
|
---|
312 | else if (target.isDeleted() && ! source.isDeleted() && target.getVersion() == source.getVersion()) {
|
---|
313 | // same version, but target is deleted. Assume target takes precedence
|
---|
314 | // otherwise too many conflicts when refreshing from the server
|
---|
315 | // but, if source has a referrer that is not in the target dataset there is a conflict
|
---|
316 | // If target dataset refers to the deleted primitive, conflict will be added in fixReferences method
|
---|
317 | for (OsmPrimitive referrer: source.getReferrers()) {
|
---|
318 | if (targetDataSet.getPrimitiveById(referrer.getPrimitiveId()) == null) {
|
---|
319 | conflicts.add(new Conflict<OsmPrimitive>(target, source, true));
|
---|
320 | target.setDeleted(false);
|
---|
321 | break;
|
---|
322 | }
|
---|
323 | }
|
---|
324 | } else if (! target.isModified() && source.isDeleted()) {
|
---|
325 | // target not modified. We can assume that source is the most recent version,
|
---|
326 | // so mark it to be deleted.
|
---|
327 | //
|
---|
328 | objectsToDelete.add(target);
|
---|
329 | } else if (! target.isModified() && source.isModified()) {
|
---|
330 | // target not modified. We can assume that source is the most recent version.
|
---|
331 | // clone it into target.
|
---|
332 | target.mergeFrom(source);
|
---|
333 | objectsWithChildrenToMerge.add(source.getPrimitiveId());
|
---|
334 | } else if (! target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) {
|
---|
335 | // both not modified. Merge nevertheless.
|
---|
336 | // This helps when updating "empty" relations, see #4295
|
---|
337 | target.mergeFrom(source);
|
---|
338 | objectsWithChildrenToMerge.add(source.getPrimitiveId());
|
---|
339 | } else if (! target.isModified() && !source.isModified() && target.getVersion() < source.getVersion()) {
|
---|
340 | // my not modified but other is newer. clone other onto mine.
|
---|
341 | //
|
---|
342 | target.mergeFrom(source);
|
---|
343 | objectsWithChildrenToMerge.add(source.getPrimitiveId());
|
---|
344 | } else if (target.isModified() && ! source.isModified() && target.getVersion() == source.getVersion()) {
|
---|
345 | // target is same as source but target is modified
|
---|
346 | // => keep target and reset modified flag if target and source are semantically equal
|
---|
347 | if (target.hasEqualSemanticAttributes(source)) {
|
---|
348 | target.setModified(false);
|
---|
349 | }
|
---|
350 | } else if (source.isDeleted() != target.isDeleted()) {
|
---|
351 | // target is modified and deleted state differs.
|
---|
352 | // this have to be resolved manually.
|
---|
353 | //
|
---|
354 | conflicts.add(target,source);
|
---|
355 | } else if (! target.hasEqualSemanticAttributes(source)) {
|
---|
356 | // target is modified and is not semantically equal with source. Can't automatically
|
---|
357 | // resolve the differences
|
---|
358 | // => create a conflict
|
---|
359 | conflicts.add(target,source);
|
---|
360 | } else {
|
---|
361 | // clone from other. mergeFrom will mainly copy
|
---|
362 | // technical attributes like timestamp or user information. Semantic
|
---|
363 | // attributes should already be equal if we get here.
|
---|
364 | //
|
---|
365 | target.mergeFrom(source);
|
---|
366 | objectsWithChildrenToMerge.add(source.getPrimitiveId());
|
---|
367 | }
|
---|
368 | return true;
|
---|
369 | }
|
---|
370 |
|
---|
371 | /**
|
---|
372 | * Runs the merge operation. Successfully merged {@see OsmPrimitive}s are in
|
---|
373 | * {@see #getMyDataSet()}.
|
---|
374 | *
|
---|
375 | * See {@see #getConflicts()} for a map of conflicts after the merge operation.
|
---|
376 | */
|
---|
377 | public void merge() {
|
---|
378 | merge(null);
|
---|
379 | }
|
---|
380 |
|
---|
381 | /**
|
---|
382 | * Runs the merge operation. Successfully merged {@see OsmPrimitive}s are in
|
---|
383 | * {@see #getMyDataSet()}.
|
---|
384 | *
|
---|
385 | * See {@see #getConflicts()} for a map of conflicts after the merge operation.
|
---|
386 | */
|
---|
387 | public void merge(ProgressMonitor progressMonitor) {
|
---|
388 | if (sourceDataSet == null)
|
---|
389 | return;
|
---|
390 | if (progressMonitor != null) {
|
---|
391 | progressMonitor.beginTask(tr("Merging data..."), sourceDataSet.allPrimitives().size());
|
---|
392 | }
|
---|
393 | targetDataSet.beginUpdate();
|
---|
394 | try {
|
---|
395 | ArrayList<? extends OsmPrimitive> candidates = new ArrayList<Node>(targetDataSet.getNodes());
|
---|
396 | for (Node node: sourceDataSet.getNodes()) {
|
---|
397 | mergePrimitive(node, candidates);
|
---|
398 | if (progressMonitor != null) {
|
---|
399 | progressMonitor.worked(1);
|
---|
400 | }
|
---|
401 | }
|
---|
402 | candidates.clear();
|
---|
403 | candidates = new ArrayList<Way>(targetDataSet.getWays());
|
---|
404 | for (Way way: sourceDataSet.getWays()) {
|
---|
405 | mergePrimitive(way, candidates);
|
---|
406 | if (progressMonitor != null) {
|
---|
407 | progressMonitor.worked(1);
|
---|
408 | }
|
---|
409 | }
|
---|
410 | candidates.clear();
|
---|
411 | candidates = new ArrayList<Relation>(targetDataSet.getRelations());
|
---|
412 | for (Relation relation: sourceDataSet.getRelations()) {
|
---|
413 | mergePrimitive(relation, candidates);
|
---|
414 | if (progressMonitor != null) {
|
---|
415 | progressMonitor.worked(1);
|
---|
416 | }
|
---|
417 | }
|
---|
418 | candidates.clear();
|
---|
419 | fixReferences();
|
---|
420 | } finally {
|
---|
421 | targetDataSet.endUpdate();
|
---|
422 | }
|
---|
423 | if (progressMonitor != null) {
|
---|
424 | progressMonitor.finishTask();
|
---|
425 | }
|
---|
426 | }
|
---|
427 |
|
---|
428 | /**
|
---|
429 | * replies my dataset
|
---|
430 | *
|
---|
431 | * @return
|
---|
432 | */
|
---|
433 | public DataSet getTargetDataSet() {
|
---|
434 | return targetDataSet;
|
---|
435 | }
|
---|
436 |
|
---|
437 | /**
|
---|
438 | * replies the map of conflicts
|
---|
439 | *
|
---|
440 | * @return the map of conflicts
|
---|
441 | */
|
---|
442 | public ConflictCollection getConflicts() {
|
---|
443 | return conflicts;
|
---|
444 | }
|
---|
445 | }
|
---|