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.ChangeMembersCommand;
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        /** Set of member objects of the relation */
113        private final Set<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 HashSet<>(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        for (Set<OsmPrimitive> duplicated : relations.values()) {
205            if (duplicated.size() > 1) {
206                TestError testError = TestError.builder(this, Severity.ERROR, DUPLICATE_RELATION)
207                        .message(tr("Duplicated relations"))
208                        .primitives(duplicated)
209                        .build();
210                errors.add(testError);
211            }
212        }
213        relations = null;
214        for (Set<OsmPrimitive> duplicated : relationsNoKeys.values()) {
215            if (duplicated.size() > 1) {
216                TestError testError = TestError.builder(this, Severity.OTHER, SAME_RELATION)
217                        .message(tr("Relations with same members"))
218                        .primitives(duplicated)
219                        .build();
220                errors.add(testError);
221            }
222        }
223        relationsNoKeys = null;
224        super.endTest();
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               || "destination_sign".equals(r.get("type")) || 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 (!isFixable(testError)) return null;
249
250        Set<Relation> relFix = testError.primitives(Relation.class)
251                .filter(r -> !r.isDeleted() || r.getDataSet() == null || r.getDataSet().getPrimitiveById(r) == null)
252                .collect(Collectors.toSet());
253
254        if (relFix.size() < 2)
255            return null;
256
257        long idToKeep = 0;
258        Relation relationToKeep = relFix.iterator().next();
259        // Find the relation that is member of one or more relations. (If any)
260        Relation relationWithRelations = null;
261        Collection<Relation> relRef = null;
262        for (Relation r : relFix) {
263            Collection<Relation> rel = r.referrers(Relation.class).collect(Collectors.toList());
264            if (!rel.isEmpty()) {
265                if (relationWithRelations != null)
266                    throw new AssertionError("Cannot fix duplicate relations: More than one relation is member of another relation.");
267                relationWithRelations = r;
268                relRef = rel;
269            }
270            // Only one relation will be kept - the one with lowest positive ID, if such exist
271            // or one "at random" if no such exists. Rest of the relations will be deleted
272            if (!r.isNew() && (idToKeep == 0 || r.getId() < idToKeep)) {
273                idToKeep = r.getId();
274                relationToKeep = r;
275            }
276        }
277
278        Collection<Command> commands = new LinkedList<>();
279
280        // Fix relations.
281        if (relationWithRelations != null && relRef != null && relationToKeep != relationWithRelations) {
282            for (Relation rel : relRef) {
283                List<RelationMember> members = new ArrayList<>(rel.getMembers());
284                for (int i = 0; i < rel.getMembers().size(); ++i) {
285                    RelationMember m = rel.getMember(i);
286                    if (relationWithRelations.equals(m.getMember())) {
287                        members.set(i, new RelationMember(m.getRole(), relationToKeep));
288                    }
289                }
290                commands.add(new ChangeMembersCommand(rel, members));
291            }
292        }
293
294        // Delete all relations in the list
295        relFix.remove(relationToKeep);
296        commands.add(new DeleteCommand(relFix));
297        return new SequenceCommand(tr("Delete duplicate relations"), commands);
298    }
299
300    @Override
301    public boolean isFixable(TestError testError) {
302        if (!(testError.getTester() instanceof DuplicateRelation)
303            || testError.getCode() == SAME_RELATION) return false;
304
305        // We fix it only if there is no more than one relation that is relation member.
306        Set<Relation> rels = testError.primitives(Relation.class)
307                .collect(Collectors.toSet());
308
309        if (rels.size() < 2)
310            return false;
311
312        // count relations with relations
313        return rels.stream()
314                .filter(x -> x.referrers(Relation.class).anyMatch(y -> true))
315                .limit(2)
316                .count() <= 1;
317    }
318}