source: josm/trunk/src/org/openstreetmap/josm/data/validation/tests/DuplicateWay.java@ 17243

Last change on this file since 17243 was 17243, checked in by GerdP, 4 years ago

see #19885: memory leak with "temporary" objects in validator and actions

  • replace ChangeCommand by ChangePropertyCommand to avoid cloning primitives
  • also move the call of super.endTest() to the end of the method endTest(), else reported timings make not much sense
  • Property svn:eol-style set to native
File size: 11.8 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.validation.tests;
3
4import static org.openstreetmap.josm.tools.I18n.tr;
5
6import java.util.ArrayList;
7import java.util.Collection;
8import java.util.Collections;
9import java.util.HashSet;
10import java.util.LinkedList;
11import java.util.List;
12import java.util.Map;
13import java.util.Objects;
14import java.util.Set;
15import java.util.stream.Collectors;
16import java.util.stream.IntStream;
17
18import org.openstreetmap.josm.command.ChangeMembersCommand;
19import org.openstreetmap.josm.command.Command;
20import org.openstreetmap.josm.command.DeleteCommand;
21import org.openstreetmap.josm.command.SequenceCommand;
22import org.openstreetmap.josm.data.coor.LatLon;
23import org.openstreetmap.josm.data.osm.AbstractPrimitive;
24import org.openstreetmap.josm.data.osm.Node;
25import org.openstreetmap.josm.data.osm.OsmPrimitive;
26import org.openstreetmap.josm.data.osm.Relation;
27import org.openstreetmap.josm.data.osm.RelationMember;
28import org.openstreetmap.josm.data.osm.Way;
29import org.openstreetmap.josm.data.validation.Severity;
30import org.openstreetmap.josm.data.validation.Test;
31import org.openstreetmap.josm.data.validation.TestError;
32import org.openstreetmap.josm.gui.progress.ProgressMonitor;
33import org.openstreetmap.josm.tools.MultiMap;
34
35/**
36 * Tests if there are duplicate ways
37 */
38public class DuplicateWay extends Test {
39
40 /**
41 * Class to store a way reduced to coordinates and keys. Essentially this is used to call the
42 * <code>equals{}</code> function.
43 */
44 private static class WayPair {
45 private final List<LatLon> coor;
46 private final Map<String, String> keys;
47
48 WayPair(List<LatLon> coor, Map<String, String> keys) {
49 this.coor = coor;
50 this.keys = keys;
51 }
52
53 @Override
54 public int hashCode() {
55 return Objects.hash(coor, keys);
56 }
57
58 @Override
59 public boolean equals(Object obj) {
60 if (this == obj) return true;
61 if (obj == null || getClass() != obj.getClass()) return false;
62 WayPair wayPair = (WayPair) obj;
63 return Objects.equals(coor, wayPair.coor) &&
64 Objects.equals(keys, wayPair.keys);
65 }
66 }
67
68 /**
69 * Class to store a way reduced to coordinates. Essentially this is used to call the
70 * <code>equals{}</code> function.
71 */
72 private static class WayPairNoTags {
73 private final List<LatLon> coor;
74
75 WayPairNoTags(List<LatLon> coor) {
76 this.coor = coor;
77 }
78
79 @Override
80 public int hashCode() {
81 return Objects.hash(coor);
82 }
83
84 @Override
85 public boolean equals(Object obj) {
86 if (this == obj) return true;
87 if (obj == null || getClass() != obj.getClass()) return false;
88 WayPairNoTags that = (WayPairNoTags) obj;
89 return Objects.equals(coor, that.coor);
90 }
91 }
92
93 /** Test identification for exactly identical ways (coordinates and tags). */
94 protected static final int DUPLICATE_WAY = 1401;
95 /** Test identification for identical ways (coordinates only). */
96 protected static final int SAME_WAY = 1402;
97
98 /** Bag of all ways */
99 private MultiMap<WayPair, OsmPrimitive> ways;
100
101 /** Bag of all ways, regardless of tags */
102 private MultiMap<WayPairNoTags, OsmPrimitive> waysNoTags;
103
104 /** Set of known hashcodes for list of coordinates **/
105 private Set<Integer> knownHashCodes;
106
107 /**
108 * Constructor
109 */
110 public DuplicateWay() {
111 super(tr("Duplicated ways"),
112 tr("This test checks that there are no ways with same node coordinates and optionally also same tags."));
113 }
114
115 @Override
116 public void startTest(ProgressMonitor monitor) {
117 super.startTest(monitor);
118 ways = new MultiMap<>(1000);
119 waysNoTags = new MultiMap<>(1000);
120 knownHashCodes = new HashSet<>(1000);
121 }
122
123 @Override
124 public void endTest() {
125 super.endTest();
126 for (Set<OsmPrimitive> duplicated : ways.values()) {
127 if (duplicated.size() > 1) {
128 TestError testError = TestError.builder(this, Severity.ERROR, DUPLICATE_WAY)
129 .message(tr("Duplicated ways"))
130 .primitives(duplicated)
131 .build();
132 errors.add(testError);
133 }
134 }
135
136 for (Set<OsmPrimitive> sameway : waysNoTags.values()) {
137 if (sameway.size() > 1) {
138 //Report error only if at least some tags are different, as otherwise the error was already reported as duplicated ways
139 Map<String, String> tags0 = null;
140 boolean skip = true;
141
142 for (OsmPrimitive o : sameway) {
143 if (tags0 == null) {
144 tags0 = o.getKeys();
145 removeUninterestingKeys(tags0);
146 } else {
147 Map<String, String> tagsCmp = o.getKeys();
148 removeUninterestingKeys(tagsCmp);
149 if (!tagsCmp.equals(tags0)) {
150 skip = false;
151 break;
152 }
153 }
154 }
155 if (skip) {
156 continue;
157 }
158 TestError testError = TestError.builder(this, Severity.WARNING, SAME_WAY)
159 .message(tr("Ways with same position"))
160 .primitives(sameway)
161 .build();
162 errors.add(testError);
163 }
164 }
165 ways = null;
166 waysNoTags = null;
167 knownHashCodes = null;
168 }
169
170 /**
171 * Remove uninteresting discardable keys to normalize the tags
172 * @param wkeys The tags of the way, obtained by {@code Way#getKeys}
173 */
174 public void removeUninterestingKeys(Map<String, String> wkeys) {
175 for (String key : AbstractPrimitive.getDiscardableKeys()) {
176 wkeys.remove(key);
177 }
178 }
179
180 @Override
181 public void visit(Way w) {
182 if (!w.isUsable())
183 return;
184 List<LatLon> wLat = getOrderedNodes(w);
185 // If this way has not direction-dependant keys, make sure the list is ordered the same for all ways (fix #8015)
186 if (!w.hasDirectionKeys()) {
187 int hash = wLat.hashCode();
188 if (!knownHashCodes.contains(hash)) {
189 List<LatLon> reversedwLat = new ArrayList<>(wLat);
190 Collections.reverse(reversedwLat);
191 int reverseHash = reversedwLat.hashCode();
192 if (!knownHashCodes.contains(reverseHash)) {
193 // Neither hash or reversed hash is known, remember hash
194 knownHashCodes.add(hash);
195 } else {
196 // Reversed hash is known, use the reverse list then
197 wLat = reversedwLat;
198 }
199 }
200 }
201 Map<String, String> wkeys = w.getKeys();
202 removeUninterestingKeys(wkeys);
203 WayPair wKey = new WayPair(wLat, wkeys);
204 ways.put(wKey, w);
205 WayPairNoTags wKeyN = new WayPairNoTags(wLat);
206 waysNoTags.put(wKeyN, w);
207 }
208
209 /**
210 * Replies the ordered list of nodes of way w such as it is easier to find duplicated ways.
211 * In case of a closed way, build the list of lat/lon starting from the node with the lowest id
212 * to ensure this list will produce the same hashcode as the list obtained from another closed
213 * way with the same nodes, in the same order, but that does not start from the same node (fix #8008)
214 * @param w way
215 * @return the ordered list of nodes of way w such as it is easier to find duplicated ways
216 * @since 7721
217 */
218 public static List<LatLon> getOrderedNodes(Way w) {
219 List<Node> wNodes = w.getNodes(); // The original list of nodes for this way
220 List<Node> wNodesToUse = new ArrayList<>(wNodes.size()); // The list that will be considered for this test
221 if (w.isClosed()) {
222 int lowestIndex = 0;
223 long lowestNodeId = wNodes.get(0).getUniqueId();
224 for (int i = 1; i < wNodes.size(); i++) {
225 if (wNodes.get(i).getUniqueId() < lowestNodeId) {
226 lowestNodeId = wNodes.get(i).getUniqueId();
227 lowestIndex = i;
228 }
229 }
230 IntStream.range(lowestIndex, wNodes.size() - 1)
231 .mapToObj(wNodes::get)
232 .forEach(wNodesToUse::add);
233 for (int i = 0; i < lowestIndex; i++) {
234 wNodesToUse.add(wNodes.get(i));
235 }
236 wNodesToUse.add(wNodes.get(lowestIndex));
237 } else {
238 wNodesToUse.addAll(wNodes);
239 }
240 // Build the list of lat/lon
241
242 return wNodesToUse.stream()
243 .map(Node::getCoor)
244 .collect(Collectors.toList());
245 }
246
247 /**
248 * Fix the error by removing all but one instance of duplicate ways
249 */
250 @Override
251 public Command fixError(TestError testError) {
252 Set<Way> wayz = testError.primitives(Way.class)
253 .filter(w -> !w.isDeleted())
254 .collect(Collectors.toSet());
255
256 if (wayz.size() < 2)
257 return null;
258
259 long idToKeep = 0;
260 Way wayToKeep = wayz.iterator().next();
261 // Find the way that is member of one or more relations. (If any)
262 Way wayWithRelations = null;
263 List<Relation> relations = null;
264 for (Way w : wayz) {
265 List<Relation> rel = w.referrers(Relation.class).collect(Collectors.toList());
266 if (!rel.isEmpty()) {
267 if (wayWithRelations != null)
268 throw new AssertionError("Cannot fix duplicate Ways: More than one way is relation member.");
269 wayWithRelations = w;
270 relations = rel;
271 }
272 // Only one way will be kept - the one with lowest positive ID, if such exist
273 // or one "at random" if no such exists. Rest of the ways will be deleted
274 if (!w.isNew() && (idToKeep == 0 || w.getId() < idToKeep)) {
275 idToKeep = w.getId();
276 wayToKeep = w;
277 }
278 }
279
280 Collection<Command> commands = new LinkedList<>();
281
282 // Fix relations.
283 if (wayWithRelations != null && relations != null && wayToKeep != wayWithRelations) {
284 for (Relation rel : relations) {
285 List<RelationMember> members = rel.getMembers();
286 for (int i = 0; i < rel.getMembers().size(); ++i) {
287 RelationMember m = rel.getMember(i);
288 if (wayWithRelations.equals(m.getMember())) {
289 members.set(i, new RelationMember(m.getRole(), wayToKeep));
290 }
291 }
292 commands.add(new ChangeMembersCommand(rel, members));
293 }
294 }
295
296 // Delete all ways in the list
297 // Note: nodes are not deleted, these can be detected and deleted at next pass
298 wayz.remove(wayToKeep);
299 commands.add(new DeleteCommand(wayz));
300 return new SequenceCommand(tr("Delete duplicate ways"), commands);
301 }
302
303 @Override
304 public boolean isFixable(TestError testError) {
305 if (!(testError.getTester() instanceof DuplicateWay))
306 return false;
307
308 // Do not automatically fix same ways with different tags
309 if (testError.getCode() != DUPLICATE_WAY) return false;
310
311 // We fix it only if there is no more than one way that is relation member.
312 Set<Way> wayz = testError.primitives(Way.class).collect(Collectors.toSet());
313 if (wayz.size() < 2)
314 return false;
315
316 long waysWithRelations = wayz.stream()
317 .filter(w -> w.referrers(Relation.class).anyMatch(x -> true))
318 .count();
319 return waysWithRelations <= 1;
320 }
321}
Note: See TracBrowser for help on using the repository browser.