001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.validation.tests;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005
006import java.util.ArrayList;
007import java.util.Collection;
008import java.util.HashSet;
009import java.util.LinkedList;
010import java.util.List;
011import java.util.Map;
012import java.util.Objects;
013import java.util.Set;
014
015import org.openstreetmap.josm.command.ChangeCommand;
016import org.openstreetmap.josm.command.Command;
017import org.openstreetmap.josm.command.DeleteCommand;
018import org.openstreetmap.josm.command.SequenceCommand;
019import org.openstreetmap.josm.data.coor.LatLon;
020import org.openstreetmap.josm.data.osm.Node;
021import org.openstreetmap.josm.data.osm.OsmPrimitive;
022import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
023import org.openstreetmap.josm.data.osm.Relation;
024import org.openstreetmap.josm.data.osm.RelationMember;
025import org.openstreetmap.josm.data.osm.Way;
026import org.openstreetmap.josm.data.validation.Severity;
027import org.openstreetmap.josm.data.validation.Test;
028import org.openstreetmap.josm.data.validation.TestError;
029import org.openstreetmap.josm.gui.progress.ProgressMonitor;
030import org.openstreetmap.josm.tools.MultiMap;
031
032/**
033 * Tests if there are duplicate relations
034 */
035public class DuplicateRelation extends Test {
036
037    /**
038     * Class to store one relation members and information about it
039     */
040    public static class RelMember {
041        /** Role of the relation member */
042        private final String role;
043
044        /** Type of the relation member */
045        private final OsmPrimitiveType type;
046
047        /** Tags of the relation member */
048        private Map<String, String> tags;
049
050        /** Coordinates of the relation member */
051        private List<LatLon> coor;
052
053        /** ID of the relation member in case it is a {@link Relation} */
054        private long relId;
055
056        @Override
057        public int hashCode() {
058            return Objects.hash(role, type, tags, coor, relId);
059        }
060
061        @Override
062        public boolean equals(Object obj) {
063            if (this == obj) return true;
064            if (obj == null || getClass() != obj.getClass()) return false;
065            RelMember relMember = (RelMember) obj;
066            return relId == relMember.relId &&
067                    type == relMember.type &&
068                    Objects.equals(role, relMember.role) &&
069                    Objects.equals(tags, relMember.tags) &&
070                    Objects.equals(coor, relMember.coor);
071        }
072
073        /** Extract and store relation information based on the relation member
074         * @param src The relation member to store information about
075         */
076        public RelMember(RelationMember src) {
077            role = src.getRole();
078            type = src.getType();
079            relId = 0;
080            coor = new ArrayList<>();
081
082            if (src.isNode()) {
083                Node r = src.getNode();
084                tags = r.getKeys();
085                coor = new ArrayList<>(1);
086                coor.add(r.getCoor());
087            }
088            if (src.isWay()) {
089                Way r = src.getWay();
090                tags = r.getKeys();
091                List<Node> wNodes = r.getNodes();
092                coor = new ArrayList<>(wNodes.size());
093                for (Node wNode : wNodes) {
094                    coor.add(wNode.getCoor());
095                }
096            }
097            if (src.isRelation()) {
098                Relation r = src.getRelation();
099                tags = r.getKeys();
100                relId = r.getId();
101                coor = new ArrayList<>();
102            }
103        }
104    }
105
106    /**
107     * Class to store relation members
108     */
109    private static class RelationMembers {
110        /** List of member objects of the relation */
111        private final List<RelMember> members;
112
113        /** Store relation information
114         * @param members The list of relation members
115         */
116        RelationMembers(List<RelationMember> members) {
117            this.members = new ArrayList<>(members.size());
118            for (RelationMember member : members) {
119                this.members.add(new RelMember(member));
120            }
121        }
122
123        @Override
124        public int hashCode() {
125            return Objects.hash(members);
126        }
127
128        @Override
129        public boolean equals(Object obj) {
130            if (this == obj) return true;
131            if (obj == null || getClass() != obj.getClass()) return false;
132            RelationMembers that = (RelationMembers) obj;
133            return Objects.equals(members, that.members);
134        }
135    }
136
137    /**
138     * Class to store relation data (keys are usually cleanup and may not be equal to original relation)
139     */
140    private static class RelationPair {
141        /** Member objects of the relation */
142        private final RelationMembers members;
143        /** Tags of the relation */
144        private final Map<String, String> keys;
145
146        /** Store relation information
147         * @param members The list of relation members
148         * @param keys The set of tags of the relation
149         */
150        RelationPair(List<RelationMember> members, Map<String, String> keys) {
151            this.members = new RelationMembers(members);
152            this.keys = keys;
153        }
154
155        @Override
156        public int hashCode() {
157            return Objects.hash(members, keys);
158        }
159
160        @Override
161        public boolean equals(Object obj) {
162            if (this == obj) return true;
163            if (obj == null || getClass() != obj.getClass()) return false;
164            RelationPair that = (RelationPair) obj;
165            return Objects.equals(members, that.members) &&
166                    Objects.equals(keys, that.keys);
167        }
168    }
169
170    /** Code number of completely duplicated relation error */
171    protected static final int DUPLICATE_RELATION = 1901;
172
173    /** Code number of relation with same members error */
174    protected static final int SAME_RELATION = 1902;
175
176    /** MultiMap of all relations */
177    private MultiMap<RelationPair, OsmPrimitive> relations;
178
179    /** MultiMap of all relations, regardless of keys */
180    private MultiMap<List<RelationMember>, OsmPrimitive> relationsNoKeys;
181
182    /** List of keys without useful information */
183    private final Set<String> ignoreKeys = new HashSet<>(OsmPrimitive.getUninterestingKeys());
184
185    /**
186     * Default constructor
187     */
188    public DuplicateRelation() {
189        super(tr("Duplicated relations"),
190                tr("This test checks that there are no relations with same tags and same members with same roles."));
191    }
192
193    @Override
194    public void startTest(ProgressMonitor monitor) {
195        super.startTest(monitor);
196        relations = new MultiMap<>(1000);
197        relationsNoKeys = new MultiMap<>(1000);
198    }
199
200    @Override
201    public void endTest() {
202        super.endTest();
203        for (Set<OsmPrimitive> duplicated : relations.values()) {
204            if (duplicated.size() > 1) {
205                TestError testError = TestError.builder(this, Severity.ERROR, DUPLICATE_RELATION)
206                        .message(tr("Duplicated relations"))
207                        .primitives(duplicated)
208                        .build();
209                errors.add(testError);
210            }
211        }
212        relations = null;
213        for (Set<OsmPrimitive> duplicated : relationsNoKeys.values()) {
214            if (duplicated.size() > 1) {
215                TestError testError = TestError.builder(this, Severity.WARNING, SAME_RELATION)
216                        .message(tr("Relations with same members"))
217                        .primitives(duplicated)
218                        .build();
219                errors.add(testError);
220            }
221        }
222        relationsNoKeys = null;
223    }
224
225    @Override
226    public void visit(Relation r) {
227        if (!r.isUsable() || r.hasIncompleteMembers() || "tmc".equals(r.get("type")) || "TMC".equals(r.get("type")))
228            return;
229        List<RelationMember> rMembers = r.getMembers();
230        Map<String, String> rkeys = r.getKeys();
231        for (String key : ignoreKeys) {
232            rkeys.remove(key);
233        }
234        RelationPair rKey = new RelationPair(rMembers, rkeys);
235        relations.put(rKey, r);
236        relationsNoKeys.put(rMembers, r);
237    }
238
239    /**
240     * Fix the error by removing all but one instance of duplicate relations
241     * @param testError The error to fix, must be of type {@link #DUPLICATE_RELATION}
242     */
243    @Override
244    public Command fixError(TestError testError) {
245        if (testError.getCode() == SAME_RELATION) return null;
246        Collection<? extends OsmPrimitive> sel = testError.getPrimitives();
247        Set<Relation> relFix = new HashSet<>();
248
249        for (OsmPrimitive osm : sel) {
250            if (osm instanceof Relation && !osm.isDeleted()) {
251                relFix.add((Relation) osm);
252            }
253        }
254
255        if (relFix.size() < 2)
256            return null;
257
258        long idToKeep = 0;
259        Relation relationToKeep = relFix.iterator().next();
260        // Find the relation that is member of one or more relations. (If any)
261        Relation relationWithRelations = null;
262        List<Relation> relRef = null;
263        for (Relation w : relFix) {
264            List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class);
265            if (!rel.isEmpty()) {
266                if (relationWithRelations != null)
267                    throw new AssertionError("Cannot fix duplicate relations: More than one relation is member of another relation.");
268                relationWithRelations = w;
269                relRef = rel;
270            }
271            // Only one relation will be kept - the one with lowest positive ID, if such exist
272            // or one "at random" if no such exists. Rest of the relations will be deleted
273            if (!w.isNew() && (idToKeep == 0 || w.getId() < idToKeep)) {
274                idToKeep = w.getId();
275                relationToKeep = w;
276            }
277        }
278
279        Collection<Command> commands = new LinkedList<>();
280
281        // Fix relations.
282        if (relationWithRelations != null && relRef != null && relationToKeep != relationWithRelations) {
283            for (Relation rel : relRef) {
284                Relation newRel = new Relation(rel);
285                for (int i = 0; i < newRel.getMembers().size(); ++i) {
286                    RelationMember m = newRel.getMember(i);
287                    if (relationWithRelations.equals(m.getMember())) {
288                        newRel.setMember(i, new RelationMember(m.getRole(), relationToKeep));
289                    }
290                }
291                commands.add(new ChangeCommand(rel, newRel));
292            }
293        }
294
295        // Delete all relations in the list
296        relFix.remove(relationToKeep);
297        commands.add(new DeleteCommand(relFix));
298        return new SequenceCommand(tr("Delete duplicate relations"), commands);
299    }
300
301    @Override
302    public boolean isFixable(TestError testError) {
303        if (!(testError.getTester() instanceof DuplicateRelation)
304            || testError.getCode() == SAME_RELATION) return false;
305
306        // We fix it only if there is no more than one relation that is relation member.
307        Collection<? extends OsmPrimitive> sel = testError.getPrimitives();
308        Set<Relation> rels = new HashSet<>();
309
310        for (OsmPrimitive osm : sel) {
311            if (osm instanceof Relation) {
312                rels.add((Relation) osm);
313            }
314        }
315
316        if (rels.size() < 2)
317            return false;
318
319        int relationsWithRelations = 0;
320        for (Relation w : rels) {
321            List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class);
322            if (!rel.isEmpty()) {
323                ++relationsWithRelations;
324            }
325        }
326        return relationsWithRelations <= 1;
327    }
328}