001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.command;
003
004import static org.openstreetmap.josm.tools.I18n.trn;
005
006import java.util.ArrayList;
007import java.util.Collection;
008import java.util.HashMap;
009import java.util.HashSet;
010import java.util.Iterator;
011import java.util.List;
012import java.util.Map;
013import java.util.Objects;
014import java.util.Set;
015
016import javax.swing.Icon;
017
018import org.openstreetmap.josm.data.conflict.Conflict;
019import org.openstreetmap.josm.data.conflict.ConflictCollection;
020import org.openstreetmap.josm.data.osm.DataSet;
021import org.openstreetmap.josm.data.osm.Node;
022import org.openstreetmap.josm.data.osm.NodeData;
023import org.openstreetmap.josm.data.osm.OsmPrimitive;
024import org.openstreetmap.josm.data.osm.PrimitiveData;
025import org.openstreetmap.josm.data.osm.PrimitiveId;
026import org.openstreetmap.josm.data.osm.Relation;
027import org.openstreetmap.josm.data.osm.RelationData;
028import org.openstreetmap.josm.data.osm.RelationMember;
029import org.openstreetmap.josm.data.osm.Storage;
030import org.openstreetmap.josm.data.osm.Way;
031import org.openstreetmap.josm.data.osm.WayData;
032import org.openstreetmap.josm.spi.preferences.Config;
033import org.openstreetmap.josm.tools.ImageProvider;
034
035/**
036 * Command, to purge a list of primitives.
037 */
038public class PurgeCommand extends Command {
039    protected List<OsmPrimitive> toPurge;
040    protected Storage<PrimitiveData> makeIncompleteData;
041
042    protected Map<PrimitiveId, PrimitiveData> makeIncompleteDataByPrimId;
043
044    protected final ConflictCollection purgedConflicts = new ConflictCollection();
045
046    /**
047     * Constructs a new {@code PurgeCommand} (does not handle conflicts).
048     * This command relies on a number of consistency conditions:
049     *  - makeIncomplete must be a subset of toPurge.
050     *  - Each primitive, that is in toPurge but not in makeIncomplete, must have all its referrers in toPurge.
051     *  - Each element of makeIncomplete must not be new and must have only referrers that are either a relation or included in toPurge.
052     * @param data OSM data set
053     * @param toPurge primitives to purge
054     * @param makeIncomplete primitives to make incomplete
055     * @since 11240
056     */
057    public PurgeCommand(DataSet data, Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) {
058        super(data);
059        init(toPurge, makeIncomplete);
060    }
061
062    private void init(Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) {
063        /**
064         * The topological sort is to avoid missing way nodes and missing
065         * relation members when adding primitives back to the dataset on undo.
066         *
067         * The same should hold for normal execution, but at time of writing
068         * there seem to be no such consistency checks when removing primitives.
069         * (It is done in a save manner, anyway.)
070         */
071        this.toPurge = topoSort(toPurge);
072        saveIncomplete(makeIncomplete);
073    }
074
075    protected final void saveIncomplete(Collection<OsmPrimitive> makeIncomplete) {
076        makeIncompleteData = new Storage<>(new Storage.PrimitiveIdHash());
077        makeIncompleteDataByPrimId = makeIncompleteData.foreignKey(new Storage.PrimitiveIdHash());
078
079        for (OsmPrimitive osm : makeIncomplete) {
080            makeIncompleteData.add(osm.save());
081        }
082    }
083
084    @Override
085    public boolean executeCommand() {
086        getAffectedDataSet().beginUpdate();
087        try {
088            purgedConflicts.get().clear();
089            // unselect primitives in advance to not fire a selection change for every one of them
090            getAffectedDataSet().clearSelection(toPurge);
091            // Loop from back to front to keep referential integrity.
092            for (int i = toPurge.size()-1; i >= 0; --i) {
093                OsmPrimitive osm = toPurge.get(i);
094                if (makeIncompleteDataByPrimId.containsKey(osm)) {
095                    // we could simply set the incomplete flag
096                    // but that would not free memory in case the
097                    // user clears undo/redo buffer after purge
098                    PrimitiveData empty;
099                    switch(osm.getType()) {
100                    case NODE: empty = new NodeData(); break;
101                    case WAY: empty = new WayData(); break;
102                    case RELATION: empty = new RelationData(); break;
103                    default: throw new AssertionError();
104                    }
105                    empty.setId(osm.getUniqueId());
106                    empty.setIncomplete(true);
107                    osm.load(empty);
108                } else {
109                    getAffectedDataSet().removePrimitive(osm);
110                    Conflict<?> conflict = getAffectedDataSet().getConflicts().getConflictForMy(osm);
111                    if (conflict != null) {
112                        purgedConflicts.add(conflict);
113                        getAffectedDataSet().getConflicts().remove(conflict);
114                    }
115                }
116            }
117            getAffectedDataSet().clearMappaintCache();
118        } finally {
119            getAffectedDataSet().endUpdate();
120        }
121        return true;
122    }
123
124    @Override
125    public void undoCommand() {
126        if (getAffectedDataSet() == null)
127            return;
128
129        getAffectedDataSet().beginUpdate();
130        try {
131            for (OsmPrimitive osm : toPurge) {
132                PrimitiveData data = makeIncompleteDataByPrimId.get(osm);
133                if (data != null) {
134                    if (getAffectedDataSet().getPrimitiveById(osm) != osm)
135                        throw new AssertionError(
136                                String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm));
137                    osm.load(data);
138                } else {
139                    if (getAffectedDataSet().getPrimitiveById(osm) != null)
140                        throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm));
141                    getAffectedDataSet().addPrimitive(osm);
142                }
143            }
144
145            for (Conflict<?> conflict : purgedConflicts) {
146                getAffectedDataSet().getConflicts().add(conflict);
147            }
148            getAffectedDataSet().clearMappaintCache();
149        } finally {
150            getAffectedDataSet().endUpdate();
151        }
152    }
153
154    /**
155     * Sorts a collection of primitives such that for each object
156     * its referrers come later in the sorted collection.
157     * @param sel collection of primitives to sort
158     * @return sorted list
159     */
160    public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) {
161        Set<OsmPrimitive> in = new HashSet<>(sel);
162        List<OsmPrimitive> out = new ArrayList<>(in.size());
163        Set<Relation> inR = new HashSet<>();
164
165        // Nodes not deleted in the first pass
166        Set<OsmPrimitive> remainingNodes = new HashSet<>(in.size());
167
168        /**
169         *  First add nodes that have no way referrer.
170         */
171        outer:
172            for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
173                OsmPrimitive u = it.next();
174                if (u instanceof Node) {
175                    Node n = (Node) u;
176                    for (OsmPrimitive ref : n.getReferrers()) {
177                        if (ref instanceof Way && in.contains(ref)) {
178                            it.remove();
179                            remainingNodes.add(n);
180                            continue outer;
181                        }
182                    }
183                    it.remove();
184                    out.add(n);
185                }
186            }
187
188        /**
189         * Then add all ways, each preceded by its (remaining) nodes.
190         */
191        for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
192            OsmPrimitive u = it.next();
193            if (u instanceof Way) {
194                Way w = (Way) u;
195                it.remove();
196                for (Node n : w.getNodes()) {
197                    if (remainingNodes.contains(n)) {
198                        remainingNodes.remove(n);
199                        out.add(n);
200                    }
201                }
202                out.add(w);
203            } else if (u instanceof Relation) {
204                inR.add((Relation) u);
205            }
206        }
207
208        if (!remainingNodes.isEmpty())
209            throw new AssertionError("topo sort algorithm failed (nodes remaining)");
210
211        // Do topological sorting on a DAG where each arrow points from child to parent.
212        //  (Because it is faster to loop over getReferrers() than getMembers().)
213
214        Map<Relation, Integer> numChilds = new HashMap<>();
215
216        // calculate initial number of childs
217        for (Relation r : inR) {
218            numChilds.put(r, 0);
219        }
220        for (Relation r : inR) {
221            for (OsmPrimitive parent : r.getReferrers()) {
222                if (!(parent instanceof Relation))
223                    throw new AssertionError();
224                Integer i = numChilds.get(parent);
225                if (i != null) {
226                    numChilds.put((Relation) parent, i+1);
227                }
228            }
229        }
230        Set<Relation> childlessR = new HashSet<>();
231        for (Relation r : inR) {
232            if (numChilds.get(r).equals(0)) {
233                childlessR.add(r);
234            }
235        }
236
237        List<Relation> outR = new ArrayList<>(inR.size());
238        while (!childlessR.isEmpty()) {
239            // Identify one childless Relation and let it virtually die. This makes other relations childless.
240            Iterator<Relation> it = childlessR.iterator();
241            Relation next = it.next();
242            it.remove();
243            outR.add(next);
244
245            for (OsmPrimitive parentPrim : next.getReferrers()) {
246                Relation parent = (Relation) parentPrim;
247                Integer i = numChilds.get(parent);
248                if (i != null) {
249                    numChilds.put(parent, i-1);
250                    if (i-1 == 0) {
251                        childlessR.add(parent);
252                    }
253                }
254            }
255        }
256
257        if (outR.size() != inR.size())
258            throw new AssertionError("topo sort algorithm failed");
259
260        out.addAll(outR);
261
262        return out;
263    }
264
265    @Override
266    public String getDescriptionText() {
267        return trn("Purged {0} object", "Purged {0} objects", toPurge.size(), toPurge.size());
268    }
269
270    @Override
271    public Icon getDescriptionIcon() {
272        return ImageProvider.get("data", "purge");
273    }
274
275    @Override
276    public Collection<? extends OsmPrimitive> getParticipatingPrimitives() {
277        return toPurge;
278    }
279
280    @Override
281    public void fillModifiedData(Collection<OsmPrimitive> modified, Collection<OsmPrimitive> deleted, Collection<OsmPrimitive> added) {
282        // Do nothing
283    }
284
285    @Override
286    public int hashCode() {
287        return Objects.hash(super.hashCode(), toPurge, makeIncompleteData, makeIncompleteDataByPrimId, purgedConflicts, getAffectedDataSet());
288    }
289
290    @Override
291    public boolean equals(Object obj) {
292        if (this == obj) return true;
293        if (obj == null || getClass() != obj.getClass()) return false;
294        if (!super.equals(obj)) return false;
295        PurgeCommand that = (PurgeCommand) obj;
296        return Objects.equals(toPurge, that.toPurge) &&
297                Objects.equals(makeIncompleteData, that.makeIncompleteData) &&
298                Objects.equals(makeIncompleteDataByPrimId, that.makeIncompleteDataByPrimId) &&
299                Objects.equals(purgedConflicts, that.purgedConflicts);
300    }
301
302    /**
303     * Creates a new {@code PurgeCommand} to purge selected OSM primitives.
304     * @param sel selected OSM primitives
305     * @param toPurgeAdditionally optional list that will be filled with primitives to be purged that have not been in the selection
306     * @return command to purge selected OSM primitives
307     * @since 12718
308     */
309    public static PurgeCommand build(Collection<OsmPrimitive> sel, List<OsmPrimitive> toPurgeAdditionally) {
310        Set<OsmPrimitive> toPurge = new HashSet<>(sel);
311        // finally, contains all objects that are purged
312        Set<OsmPrimitive> toPurgeChecked = new HashSet<>();
313
314        // Add referrer, unless the object to purge is not new and the parent is a relation
315        Set<OsmPrimitive> toPurgeRecursive = new HashSet<>();
316        while (!toPurge.isEmpty()) {
317
318            for (OsmPrimitive osm: toPurge) {
319                for (OsmPrimitive parent: osm.getReferrers()) {
320                    if (toPurge.contains(parent) || toPurgeChecked.contains(parent) || toPurgeRecursive.contains(parent)) {
321                        continue;
322                    }
323                    if (parent instanceof Way || (parent instanceof Relation && osm.isNew())) {
324                        if (toPurgeAdditionally != null) {
325                            toPurgeAdditionally.add(parent);
326                        }
327                        toPurgeRecursive.add(parent);
328                    }
329                }
330                toPurgeChecked.add(osm);
331            }
332            toPurge = toPurgeRecursive;
333            toPurgeRecursive = new HashSet<>();
334        }
335
336        // Subset of toPurgeChecked. Marks primitives that remain in the dataset, but incomplete.
337        Set<OsmPrimitive> makeIncomplete = new HashSet<>();
338
339        // Find the objects that will be incomplete after purging.
340        // At this point, all parents of new to-be-purged primitives are
341        // also to-be-purged and
342        // all parents of not-new to-be-purged primitives are either
343        // to-be-purged or of type relation.
344        TOP:
345            for (OsmPrimitive child : toPurgeChecked) {
346                if (child.isNew()) {
347                    continue;
348                }
349                for (OsmPrimitive parent : child.getReferrers()) {
350                    if (parent instanceof Relation && !toPurgeChecked.contains(parent)) {
351                        makeIncomplete.add(child);
352                        continue TOP;
353                    }
354                }
355            }
356
357        // Add untagged way nodes. Do not add nodes that have other referrers not yet to-be-purged.
358        if (Config.getPref().getBoolean("purge.add_untagged_waynodes", true)) {
359            Set<OsmPrimitive> wayNodes = new HashSet<>();
360            for (OsmPrimitive osm : toPurgeChecked) {
361                if (osm instanceof Way) {
362                    Way w = (Way) osm;
363                    NODE:
364                        for (Node n : w.getNodes()) {
365                            if (n.isTagged() || toPurgeChecked.contains(n)) {
366                                continue;
367                            }
368                            for (OsmPrimitive ref : n.getReferrers()) {
369                                if (ref != w && !toPurgeChecked.contains(ref)) {
370                                    continue NODE;
371                                }
372                            }
373                            wayNodes.add(n);
374                        }
375                }
376            }
377            toPurgeChecked.addAll(wayNodes);
378            if (toPurgeAdditionally != null) {
379                toPurgeAdditionally.addAll(wayNodes);
380            }
381        }
382
383        if (Config.getPref().getBoolean("purge.add_relations_with_only_incomplete_members", true)) {
384            Set<Relation> relSet = new HashSet<>();
385            for (OsmPrimitive osm : toPurgeChecked) {
386                for (OsmPrimitive parent : osm.getReferrers()) {
387                    if (parent instanceof Relation
388                            && !(toPurgeChecked.contains(parent))
389                            && hasOnlyIncompleteMembers((Relation) parent, toPurgeChecked, relSet)) {
390                        relSet.add((Relation) parent);
391                    }
392                }
393            }
394
395            // Add higher level relations (list gets extended while looping over it)
396            List<Relation> relLst = new ArrayList<>(relSet);
397            for (int i = 0; i < relLst.size(); ++i) { // foreach loop not applicable since list gets extended while looping over it
398                for (OsmPrimitive parent : relLst.get(i).getReferrers()) {
399                    if (!(toPurgeChecked.contains(parent))
400                            && hasOnlyIncompleteMembers((Relation) parent, toPurgeChecked, relLst)) {
401                        relLst.add((Relation) parent);
402                    }
403                }
404            }
405            relSet = new HashSet<>(relLst);
406            toPurgeChecked.addAll(relSet);
407            if (toPurgeAdditionally != null) {
408                toPurgeAdditionally.addAll(relSet);
409            }
410        }
411
412        return new PurgeCommand(toPurgeChecked.iterator().next().getDataSet(), toPurgeChecked, makeIncomplete);
413    }
414
415    private static boolean hasOnlyIncompleteMembers(
416            Relation r, Collection<OsmPrimitive> toPurge, Collection<? extends OsmPrimitive> moreToPurge) {
417        for (RelationMember m : r.getMembers()) {
418            if (!m.getMember().isIncomplete() && !toPurge.contains(m.getMember()) && !moreToPurge.contains(m.getMember()))
419                return false;
420        }
421        return true;
422    }
423}