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}