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