001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.data.osm;
003    
004    import static org.openstreetmap.josm.tools.I18n.tr;
005    
006    import java.util.ArrayList;
007    import java.util.Collection;
008    import java.util.HashMap;
009    import java.util.HashSet;
010    import java.util.Iterator;
011    import java.util.LinkedList;
012    import java.util.List;
013    import java.util.Map;
014    import java.util.Set;
015    
016    import org.openstreetmap.josm.data.conflict.Conflict;
017    import org.openstreetmap.josm.data.conflict.ConflictCollection;
018    import org.openstreetmap.josm.gui.progress.ProgressMonitor;
019    import 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     */
026    public 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>theirDataSet</code> onto <code>myDataSet</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 <code>other</code> of type <P> onto my primitives.
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 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 <P>  the type of the other primitive
078         * @param source  the other 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
083                // defined id
084                //
085                if (mergeById(source))
086                    return;
087                //if (!source.isVisible())
088                // ignore it
089                //    return;
090            } else {
091                // ignore deleted primitives from source
092                if (source.isDeleted()) return;
093    
094                // try to merge onto a primitive  which has no id assigned
095                // yet but which is equal in its semantic attributes
096                //
097                for (OsmPrimitive target : candidates) {
098                    if (!target.isNew() || target.isDeleted()) {
099                        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 addConflict(Conflict<?> c) {
139            c.setMergedMap(mergedMap);
140            conflicts.add(c);
141        }
142    
143        protected void addConflict(OsmPrimitive my, OsmPrimitive their) {
144            addConflict(new Conflict<OsmPrimitive>(my, their));
145        }
146    
147        protected void fixIncomplete(Way other) {
148            Way myWay = (Way)getMergeTarget(other);
149            if (myWay == null)
150                throw new RuntimeException(tr("Missing merge target for way with id {0}", other.getUniqueId()));
151        }
152    
153        /**
154         * Postprocess the dataset and fix all merged references to point to the actual
155         * data.
156         */
157        public void fixReferences() {
158            for (Way w : sourceDataSet.getWays()) {
159                if (!conflicts.hasConflictForTheir(w) && objectsWithChildrenToMerge.contains(w.getPrimitiveId())) {
160                    mergeNodeList(w);
161                    fixIncomplete(w);
162                }
163            }
164            for (Relation r : sourceDataSet.getRelations()) {
165                if (!conflicts.hasConflictForTheir(r) && objectsWithChildrenToMerge.contains(r.getPrimitiveId())) {
166                    mergeRelationMembers(r);
167                }
168            }
169    
170            deleteMarkedObjects();
171        }
172    
173        /**
174         * Deleted objects in objectsToDelete set and create conflicts for objects that cannot
175         * be deleted because they're referenced in the target dataset.
176         */
177        protected void deleteMarkedObjects() {
178            boolean flag;
179            do {
180                flag = false;
181                for (Iterator<OsmPrimitive> it = objectsToDelete.iterator();it.hasNext();) {
182                    OsmPrimitive target = it.next();
183                    OsmPrimitive source = sourceDataSet.getPrimitiveById(target.getPrimitiveId());
184                    if (source == null)
185                        throw new RuntimeException(tr("Object of type {0} with id {1} was marked to be deleted, but it''s missing in the source dataset",
186                                target.getType(), target.getUniqueId()));
187    
188                    List<OsmPrimitive> referrers = target.getReferrers();
189                    if (referrers.isEmpty()) {
190                        resetPrimitive(target);
191                        target.mergeFrom(source);
192                        target.setDeleted(true);
193                        it.remove();
194                        flag = true;
195                    } else {
196                        for (OsmPrimitive referrer : referrers) {
197                            // If one of object referrers isn't going to be deleted,
198                            // add a conflict and don't delete the object
199                            if (!objectsToDelete.contains(referrer)) {
200                                addConflict(target, source);
201                                it.remove();
202                                flag = true;
203                                break;
204                            }
205                        }
206                    }
207    
208                }
209            } while (flag);
210    
211            if (!objectsToDelete.isEmpty()) {
212                // There are some more objects rest in the objectsToDelete set
213                // This can be because of cross-referenced relations.
214                for (OsmPrimitive osm: objectsToDelete) {
215                    resetPrimitive(osm);
216                }
217                for (OsmPrimitive osm: objectsToDelete) {
218                    osm.setDeleted(true);
219                    osm.mergeFrom(sourceDataSet.getPrimitiveById(osm.getPrimitiveId()));
220                }
221            }
222        }
223        
224        private final void resetPrimitive(OsmPrimitive osm) {
225            if (osm instanceof Way) {
226                ((Way) osm).setNodes(null);
227            } else if (osm instanceof Relation) {
228                ((Relation) osm).setMembers(null);
229            }
230        }
231    
232        /**
233         * Merges the node list of a source way onto its target way.
234         *
235         * @param source the source way
236         * @throws IllegalStateException thrown if no target way can be found for the source way
237         * @throws IllegalStateException thrown if there isn't a target node for one of the nodes in the source way
238         *
239         */
240        private void mergeNodeList(Way source) throws IllegalStateException {
241            Way target = (Way)getMergeTarget(source);
242            if (target == null)
243                throw new IllegalStateException(tr("Missing merge target for way with id {0}", source.getUniqueId()));
244    
245            List<Node> newNodes = new ArrayList<Node>(source.getNodesCount());
246            for (Node sourceNode : source.getNodes()) {
247                Node targetNode = (Node)getMergeTarget(sourceNode);
248                if (targetNode != null) {
249                    newNodes.add(targetNode);
250                    if (targetNode.isDeleted() && !conflicts.hasConflictForMy(targetNode)) {
251                        addConflict(new Conflict<OsmPrimitive>(targetNode, sourceNode, true));
252                        targetNode.setDeleted(false);
253                    }
254                } else
255                    throw new IllegalStateException(tr("Missing merge target for node with id {0}", sourceNode.getUniqueId()));
256            }
257            target.setNodes(newNodes);
258        }
259    
260        /**
261         * Merges the relation members of a source relation onto the corresponding target relation.
262         * @param source the source relation
263         * @throws IllegalStateException thrown if there is no corresponding target relation
264         * @throws IllegalStateException thrown if there isn't a corresponding target object for one of the relation
265         * members in source
266         */
267        private void mergeRelationMembers(Relation source) throws IllegalStateException {
268            Relation target = (Relation) getMergeTarget(source);
269            if (target == null)
270                throw new IllegalStateException(tr("Missing merge target for relation with id {0}", source.getUniqueId()));
271            LinkedList<RelationMember> newMembers = new LinkedList<RelationMember>();
272            for (RelationMember sourceMember : source.getMembers()) {
273                OsmPrimitive targetMember = getMergeTarget(sourceMember.getMember());
274                if (targetMember == null)
275                    throw new IllegalStateException(tr("Missing merge target of type {0} with id {1}", sourceMember.getType(), sourceMember.getUniqueId()));
276                RelationMember newMember = new RelationMember(sourceMember.getRole(), targetMember);
277                newMembers.add(newMember);
278                if (targetMember.isDeleted() && !conflicts.hasConflictForMy(targetMember)) {
279                    addConflict(new Conflict<OsmPrimitive>(targetMember, sourceMember.getMember(), true));
280                    targetMember.setDeleted(false);
281                }
282            }
283            target.setMembers(newMembers);
284        }
285    
286        /**
287         * Tries to merge a primitive <code>source</code> into an existing primitive with the same id.
288         *
289         * @param source  the source primitive which is to be merged into a target primitive
290         * @return true, if this method was able to merge <code>source</code> into a target object; false, otherwise
291         */
292        private boolean mergeById(OsmPrimitive source) {
293            OsmPrimitive target = targetDataSet.getPrimitiveById(source.getId(), source.getType());
294            // merge other into an existing primitive with the same id, if possible
295            //
296            if (target == null)
297                return false;
298            // found a corresponding target, remember it
299            mergedMap.put(source.getPrimitiveId(), target.getPrimitiveId());
300    
301            if (target.getVersion() > source.getVersion())
302                // target.version > source.version => keep target version
303                return true;
304    
305            if (target.isIncomplete() && !source.isIncomplete()) {
306                // target is incomplete, source completes it
307                // => merge source into target
308                //
309                target.mergeFrom(source);
310                objectsWithChildrenToMerge.add(source.getPrimitiveId());
311            } else if (!target.isIncomplete() && source.isIncomplete()) {
312                // target is complete and source is incomplete
313                // => keep target, it has more information already
314                //
315            } else if (target.isIncomplete() && source.isIncomplete()) {
316                // target and source are incomplete. Doesn't matter which one to
317                // take. We take target.
318                //
319            } else if (!target.isModified() && !source.isModified() && target.isVisible() != source.isVisible() && 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 has a referrer that is not in the target dataset there is a conflict
330                // If target dataset refers to the deleted primitive, conflict will be added in fixReferences method
331                for (OsmPrimitive referrer: source.getReferrers()) {
332                    if (targetDataSet.getPrimitiveById(referrer.getPrimitiveId()) == null) {
333                        addConflict(new Conflict<OsmPrimitive>(target, source, true));
334                        target.setDeleted(false);
335                        break;
336                    }
337                }
338            } else if (! target.isModified() && source.isDeleted()) {
339                // target not modified. We can assume that source is the most recent version,
340                // so mark it to be deleted.
341                //
342                objectsToDelete.add(target);
343            } else if (! target.isModified() && source.isModified()) {
344                // target not modified. We can assume that source is the most recent version.
345                // clone it into target.
346                target.mergeFrom(source);
347                objectsWithChildrenToMerge.add(source.getPrimitiveId());
348            } else if (! target.isModified() && !source.isModified() && target.getVersion() == source.getVersion()) {
349                // both not modified. Merge nevertheless.
350                // This helps when updating "empty" relations, see #4295
351                target.mergeFrom(source);
352                objectsWithChildrenToMerge.add(source.getPrimitiveId());
353            } else if (! target.isModified() && !source.isModified() && target.getVersion() < source.getVersion()) {
354                // my not modified but other is newer. clone other onto mine.
355                //
356                target.mergeFrom(source);
357                objectsWithChildrenToMerge.add(source.getPrimitiveId());
358            } else if (target.isModified() && ! source.isModified() && target.getVersion() == source.getVersion()) {
359                // target is same as source but target is modified
360                // => keep target and reset modified flag if target and source are semantically equal
361                if (target.hasEqualSemanticAttributes(source)) {
362                    target.setModified(false);
363                }
364            } else if (source.isDeleted() != target.isDeleted()) {
365                // target is modified and deleted state differs.
366                // this have to be resolved manually.
367                //
368                addConflict(target,source);
369            } else if (! target.hasEqualSemanticAttributes(source)) {
370                // target is modified and is not semantically equal with source. Can't automatically
371                // resolve the differences
372                // =>  create a conflict
373                addConflict(target,source);
374            } else {
375                // clone from other. mergeFrom will mainly copy
376                // technical attributes like timestamp or user information. Semantic
377                // attributes should already be equal if we get here.
378                //
379                target.mergeFrom(source);
380                objectsWithChildrenToMerge.add(source.getPrimitiveId());
381            }
382            return true;
383        }
384    
385        /**
386         * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in
387         * {@link #getMyDataSet()}.
388         *
389         * See {@link #getConflicts()} for a map of conflicts after the merge operation.
390         */
391        public void merge() {
392            merge(null);
393        }
394    
395        /**
396         * Runs the merge operation. Successfully merged {@link OsmPrimitive}s are in
397         * {@link #getMyDataSet()}.
398         *
399         * See {@link #getConflicts()} for a map of conflicts after the merge operation.
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                    ArrayList<? extends OsmPrimitive> candidates = new ArrayList<Node>(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<Way>(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<Relation>(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
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    }