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