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