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}