source: josm/trunk/src/org/openstreetmap/josm/data/validation/tests/RelationChecker.java

Last change on this file was 18801, checked in by taylor.smock, 8 months ago

Fix #22832: Code cleanup and some simplification, documentation fixes (patch by gaben)

There should not be any functional changes in this patch; it is intended to do
the following:

  • Simplify and cleanup code (example: Arrays.asList(item) -> Collections.singletonList(item))
  • Fix typos in documentation (which also corrects the documentation to match what actually happens, in some cases)
  • Property svn:eol-style set to native
File size: 20.7 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.marktr;
5import static org.openstreetmap.josm.tools.I18n.tr;
6
7import java.util.ArrayList;
8import java.util.Collection;
9import java.util.Collections;
10import java.util.EnumSet;
11import java.util.HashMap;
12import java.util.HashSet;
13import java.util.Iterator;
14import java.util.LinkedHashMap;
15import java.util.LinkedHashSet;
16import java.util.LinkedList;
17import java.util.List;
18import java.util.Map;
19import java.util.Set;
20import java.util.stream.Collectors;
21
22import org.openstreetmap.josm.command.ChangeMembersCommand;
23import org.openstreetmap.josm.command.Command;
24import org.openstreetmap.josm.command.DeleteCommand;
25import org.openstreetmap.josm.data.osm.OsmPrimitive;
26import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
27import org.openstreetmap.josm.data.osm.Relation;
28import org.openstreetmap.josm.data.osm.RelationMember;
29import org.openstreetmap.josm.data.preferences.BooleanProperty;
30import org.openstreetmap.josm.data.validation.OsmValidator;
31import org.openstreetmap.josm.data.validation.Severity;
32import org.openstreetmap.josm.data.validation.Test;
33import org.openstreetmap.josm.data.validation.TestError;
34import org.openstreetmap.josm.gui.progress.ProgressMonitor;
35import org.openstreetmap.josm.gui.tagging.presets.TaggingPreset;
36import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetItem;
37import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetListener;
38import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetType;
39import org.openstreetmap.josm.gui.tagging.presets.TaggingPresets;
40import org.openstreetmap.josm.gui.tagging.presets.items.KeyedItem;
41import org.openstreetmap.josm.gui.tagging.presets.items.Roles;
42import org.openstreetmap.josm.gui.tagging.presets.items.Roles.Role;
43import org.openstreetmap.josm.tools.SubclassFilteredCollection;
44import org.openstreetmap.josm.tools.Utils;
45
46/**
47 * Check for wrong relations.
48 * @since 3669
49 */
50public class RelationChecker extends Test implements TaggingPresetListener {
51
52 // CHECKSTYLE.OFF: SingleSpaceSeparator
53 /** Role ''{0}'' is not among expected values ''{1}'' */
54 public static final int ROLE_UNKNOWN = 1701;
55 /** Empty role found when expecting one of ''{0}'' */
56 public static final int ROLE_EMPTY = 1702;
57 /** Number of ''{0}'' roles too high ({1}) */
58 public static final int HIGH_COUNT = 1704;
59 /** Number of ''{0}'' roles too low ({1}) */
60 public static final int LOW_COUNT = 1705;
61 /** Role ''{0}'' missing */
62 public static final int ROLE_MISSING = 1706;
63 /** Relation type is unknown */
64 public static final int RELATION_UNKNOWN = 1707;
65 /** Role of relation member does not match template expression ''{0}'' in preset {1} */
66 public static final int WRONG_ROLE = 1708;
67 /** Type ''{0}'' of relation member with role ''{1}'' does not match accepted types ''{2}'' in preset {3} */
68 public static final int WRONG_TYPE = 1709;
69 /** Relations build circular dependencies */
70 public static final int RELATION_LOOP = 1710;
71 /** Relation is empty */
72 public static final int RELATION_EMPTY = 1711; // was 1708 up to r18505
73 // CHECKSTYLE.ON: SingleSpaceSeparator
74
75 // see 19312 comment:17
76 private static final BooleanProperty ALLOW_COMPLEX_LOOP = new BooleanProperty("validator.relation.allow.complex.dependency", false);
77
78 /**
79 * Error message used to group errors related to role problems.
80 * @since 6731
81 */
82 public static final String ROLE_VERIF_PROBLEM_MSG = tr("Role verification problem");
83 private boolean ignoreMultiPolygons;
84 private boolean ignoreTurnRestrictions;
85 private final List<List<Relation>> loops = new ArrayList<>();
86 /**
87 * Constructor
88 */
89 public RelationChecker() {
90 super(tr("Relation checker"),
91 tr("Checks for errors in relations."));
92 }
93
94 @Override
95 public void initialize() {
96 TaggingPresets.addListener(this);
97 initializePresets();
98 }
99
100 private static final Collection<TaggingPreset> relationpresets = new LinkedList<>();
101
102 /**
103 * Reads the presets data.
104 */
105 public static synchronized void initializePresets() {
106 if (!relationpresets.isEmpty()) {
107 // the presets have already been initialized
108 return;
109 }
110 for (TaggingPreset p : TaggingPresets.getTaggingPresets()) {
111 if (p.data.stream().anyMatch(i -> i instanceof Roles)) {
112 relationpresets.add(p);
113 }
114 }
115 }
116
117 private static class RoleInfo {
118 private int total;
119 }
120
121 @Override
122 public void startTest(ProgressMonitor progressMonitor) {
123 super.startTest(progressMonitor);
124
125 for (Test t : OsmValidator.getEnabledTests(false)) {
126 if (t instanceof MultipolygonTest) {
127 ignoreMultiPolygons = true;
128 }
129 if (t instanceof TurnrestrictionTest) {
130 ignoreTurnRestrictions = true;
131 }
132 }
133 }
134
135 @Override
136 public void visit(Relation n) {
137 Map<String, RoleInfo> map = buildRoleInfoMap(n);
138 if (map.isEmpty()) {
139 errors.add(TestError.builder(this, Severity.ERROR, RELATION_EMPTY)
140 .message(tr("Relation is empty"))
141 .primitives(n)
142 .build());
143 }
144 if (ignoreMultiPolygons && n.isMultipolygon()) {
145 // see #17010: don't report same problem twice
146 return;
147 }
148 if (ignoreTurnRestrictions && n.hasTag("type", "restriction")) {
149 // see #17561: don't report same problem twice
150 return;
151 }
152 Map<Role, String> allroles = buildAllRoles(n);
153 if (allroles.isEmpty() && n.hasTag("type", "route")
154 && n.hasTag("route", "train", "subway", "monorail", "tram", "bus", "trolleybus", "aerialway", "ferry")) {
155 errors.add(TestError.builder(this, Severity.WARNING, RELATION_UNKNOWN)
156 .message(tr("Route scheme is unspecified. Add {0} ({1}=public_transport; {2}=legacy)", "public_transport:version", "2", "1"))
157 .primitives(n)
158 .build());
159 } else if (n.hasKey("type") && allroles.isEmpty()) {
160 errors.add(TestError.builder(this, Severity.OTHER, RELATION_UNKNOWN)
161 .message(tr("Relation type is unknown"))
162 .primitives(n)
163 .build());
164 }
165
166 if (!map.isEmpty() && !allroles.isEmpty()) {
167 checkRoles(n, allroles, map);
168 }
169 checkLoop(n);
170 }
171
172 private static Map<String, RoleInfo> buildRoleInfoMap(Relation n) {
173 Map<String, RoleInfo> map = new HashMap<>();
174 for (RelationMember m : n.getMembers()) {
175 map.computeIfAbsent(m.getRole(), k -> new RoleInfo()).total++;
176 }
177 return map;
178 }
179
180 // return Roles grouped by key
181 private static Map<Role, String> buildAllRoles(Relation n) {
182 Map<Role, String> allroles = new LinkedHashMap<>();
183
184 for (TaggingPreset p : relationpresets) {
185 final boolean matches = TaggingPresetItem.matches(Utils.filteredCollection(p.data, KeyedItem.class), n.getKeys());
186 final SubclassFilteredCollection<TaggingPresetItem, Roles> roles = Utils.filteredCollection(p.data, Roles.class);
187 if (matches && !roles.isEmpty()) {
188 for (Role role: roles.iterator().next().roles) {
189 allroles.put(role, p.name);
190 }
191 }
192 }
193 return allroles;
194 }
195
196 private static boolean checkMemberType(Role r, RelationMember member) {
197 if (r.types != null) {
198 switch (member.getDisplayType()) {
199 case NODE:
200 return r.types.contains(TaggingPresetType.NODE);
201 case CLOSEDWAY:
202 return r.types.contains(TaggingPresetType.CLOSEDWAY);
203 case WAY:
204 return r.types.contains(TaggingPresetType.WAY);
205 case MULTIPOLYGON:
206 return r.types.contains(TaggingPresetType.MULTIPOLYGON);
207 case RELATION:
208 return r.types.contains(TaggingPresetType.RELATION);
209 default: // not matching type
210 return false;
211 }
212 } else {
213 // if no types specified, then test is passed
214 return true;
215 }
216 }
217
218 /**
219 * get all role definition for specified key and check, if some definition matches
220 *
221 * @param allroles containing list of possible role presets of the member
222 * @param member to be verified
223 * @param n relation to be verified
224 * @return <code>true</code> if member passed any of definition within preset
225 *
226 */
227 private boolean checkMemberExpressionAndType(Map<Role, String> allroles, RelationMember member, Relation n) {
228 String role = member.getRole();
229 String name = null;
230 // Set of all accepted types in preset
231 Collection<TaggingPresetType> types = EnumSet.noneOf(TaggingPresetType.class);
232 TestError possibleMatchError = null;
233 // iterate through all of the role definition within preset
234 // and look for any matching definition
235 for (Map.Entry<Role, String> e : allroles.entrySet()) {
236 Role r = e.getKey();
237 if (!r.isRole(role)) {
238 continue;
239 }
240 name = e.getValue();
241 types.addAll(r.types);
242 if (checkMemberType(r, member)) {
243 // member type accepted by role definition
244 if (r.memberExpression == null) {
245 // no member expression - so all requirements met
246 return true;
247 } else {
248 // verify if preset accepts such member
249 OsmPrimitive primitive = member.getMember();
250 if (!primitive.isUsable()) {
251 // if member is not usable (i.e. not present in working set)
252 // we can't verify expression - so we just skip it
253 return true;
254 } else {
255 // verify expression
256 if (r.memberExpression.match(primitive)) {
257 return true;
258 } else {
259 // possible match error
260 // we still need to iterate further, as we might have
261 // different preset, for which memberExpression will match
262 // but stash the error in case no better reason will be found later
263 possibleMatchError = TestError.builder(this, Severity.WARNING, WRONG_ROLE)
264 .message(ROLE_VERIF_PROBLEM_MSG,
265 marktr("Role of relation member does not match template expression ''{0}'' in preset {1}"),
266 r.memberExpression, name)
267 .primitives(member.getMember().isUsable() ? member.getMember() : n)
268 .build();
269 }
270 }
271 }
272 } else if (OsmPrimitiveType.RELATION == member.getType() && !member.getMember().isUsable()
273 && r.types.contains(TaggingPresetType.MULTIPOLYGON)) {
274 // if relation is incomplete we cannot verify if it's a multipolygon - so we just skip it
275 return true;
276 }
277 }
278
279 if (name == null) {
280 return true;
281 } else if (possibleMatchError != null) {
282 // if any error found, then assume that member type was correct
283 // and complain about not matching the memberExpression
284 // (the only failure, that we could gather)
285 errors.add(possibleMatchError);
286 } else {
287 // no errors found till now. So member at least failed at matching the type
288 // it could also fail at memberExpression, but we can't guess at which
289
290 // Do not raise an error for incomplete ways for which we expect them to be closed, as we cannot know
291 boolean ignored = member.getMember().isIncomplete() && OsmPrimitiveType.WAY == member.getType()
292 && !types.contains(TaggingPresetType.WAY) && types.contains(TaggingPresetType.CLOSEDWAY);
293 if (!ignored) {
294 // convert in localization friendly way to string of accepted types
295 String typesStr = types.stream().map(x -> tr(x.getName())).collect(Collectors.joining("/"));
296
297 errors.add(TestError.builder(this, Severity.WARNING, WRONG_TYPE)
298 .message(ROLE_VERIF_PROBLEM_MSG,
299 marktr("Type ''{0}'' of relation member with role ''{1}'' does not match accepted types ''{2}'' in preset {3}"),
300 member.getType(), member.getRole(), typesStr, name)
301 .primitives(member.getMember().isUsable() ? member.getMember() : n)
302 .build());
303 }
304 }
305 return false;
306 }
307
308 /**
309 *
310 * @param n relation to validate
311 * @param allroles contains presets for specified relation
312 * @param map contains statistics of occurrences of specified role in relation
313 */
314 private void checkRoles(Relation n, Map<Role, String> allroles, Map<String, RoleInfo> map) {
315 // go through all members of relation
316 for (RelationMember member: n.getMembers()) {
317 // error reporting done inside
318 checkMemberExpressionAndType(allroles, member, n);
319 }
320
321 // verify role counts based on whole role sets
322 for (Role r: allroles.keySet()) {
323 String keyname = r.key;
324 if (keyname.isEmpty()) {
325 keyname = tr("<empty>");
326 }
327 checkRoleCounts(n, r, keyname, map.get(r.key));
328 }
329 if ("network".equals(n.get("type")) && !"bicycle".equals(n.get("route"))) {
330 return;
331 }
332 // verify unwanted members
333 for (String key : map.keySet()) {
334 if (allroles.keySet().stream().noneMatch(role -> role.isRole(key))) {
335 String templates = allroles.keySet().stream()
336 .map(r -> r.key)
337 .map(r -> Utils.isEmpty(r) ? tr("<empty>") : r)
338 .distinct()
339 .collect(Collectors.joining("/"));
340 List<OsmPrimitive> primitives = new ArrayList<>(n.findRelationMembers(key));
341 primitives.add(0, n);
342
343 if (!key.isEmpty()) {
344 errors.add(TestError.builder(this, Severity.WARNING, ROLE_UNKNOWN)
345 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Role ''{0}'' is not among expected values ''{1}''"), key, templates)
346 .primitives(primitives)
347 .build());
348 } else {
349 errors.add(TestError.builder(this, Severity.WARNING, ROLE_EMPTY)
350 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Empty role found when expecting one of ''{0}''"), templates)
351 .primitives(primitives)
352 .build());
353 }
354 }
355 }
356 }
357
358 private void checkRoleCounts(Relation n, Role r, String keyname, RoleInfo ri) {
359 long count = (ri == null) ? 0 : ri.total;
360 long vc = r.getValidCount(count);
361 if (count != vc) {
362 if (count == 0) {
363 errors.add(TestError.builder(this, Severity.WARNING, ROLE_MISSING)
364 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Role ''{0}'' missing"), keyname)
365 .primitives(n)
366 .build());
367 } else if (vc > count) {
368 errors.add(TestError.builder(this, Severity.WARNING, LOW_COUNT)
369 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Number of ''{0}'' roles too low ({1})"), keyname, count)
370 .primitives(n)
371 .build());
372 } else {
373 errors.add(TestError.builder(this, Severity.WARNING, HIGH_COUNT)
374 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Number of ''{0}'' roles too high ({1})"), keyname, count)
375 .primitives(n)
376 .build());
377 }
378 }
379 }
380
381 @Override
382 public Command fixError(TestError testError) {
383 Collection<? extends OsmPrimitive> primitives = testError.getPrimitives();
384 if (isFixable(testError) && !primitives.iterator().next().isDeleted()) {
385 if (testError.getCode() == RELATION_EMPTY) {
386 return new DeleteCommand(primitives);
387 }
388 if (testError.getCode() == RELATION_LOOP) {
389 Relation old = (Relation) primitives.iterator().next();
390 List<RelationMember> remaining = new ArrayList<>(old.getMembers());
391 remaining.removeIf(rm -> primitives.contains(rm.getMember()));
392 return new ChangeMembersCommand(old, Utils.toUnmodifiableList(remaining));
393 }
394 }
395 return null;
396 }
397
398 @Override
399 public boolean isFixable(TestError testError) {
400 Collection<? extends OsmPrimitive> primitives = testError.getPrimitives();
401 return (testError.getCode() == RELATION_EMPTY && !primitives.isEmpty() && primitives.iterator().next().isNew())
402 || (testError.getCode() == RELATION_LOOP && primitives.size() == 1);
403 }
404
405 @Override
406 public void taggingPresetsModified() {
407 relationpresets.clear();
408 initializePresets();
409 }
410
411 @Override
412 public void endTest() {
413 if (Boolean.TRUE.equals(ALLOW_COMPLEX_LOOP.get())) {
414 loops.removeIf(loop -> loop.size() > 2);
415 }
416 loops.forEach(loop -> errors.add(TestError.builder(this, Severity.ERROR, RELATION_LOOP)
417 .message(loop.size() == 2 ? tr("Relation contains itself as a member")
418 : tr("Relations generate circular dependency of parent/child elements"))
419 .primitives(new LinkedHashSet<>(loop))
420 .build()));
421 loops.clear();
422 super.endTest();
423 }
424
425 /**
426 * Check if a given relation is part of a circular dependency loop.
427 * @param r the relation
428 */
429 private void checkLoop(Relation r) {
430 checkLoop(r, new LinkedList<>());
431 }
432
433 private void checkLoop(Relation parent, List<Relation> path) {
434 Set<Relation> pathSet = new HashSet<>(path);
435 if (pathSet.contains(parent)) {
436 Iterator<List<Relation>> iter = loops.iterator();
437 Set<Relation> loop = new HashSet<>();
438 while (iter.hasNext()) {
439 loop.addAll(iter.next());
440 if (loop.size() > path.size() && loop.containsAll(path)) {
441 // remove same loop with irrelevant parent
442 iter.remove();
443 } else if (path.size() >= loop.size() && pathSet.containsAll(loop)) {
444 // same or smaller loop is already known
445 return;
446 }
447 loop.clear();
448 }
449 if (path.get(0).equals(parent)) {
450 path.add(parent);
451 loops.add(path);
452 }
453 return;
454 }
455 path.add(parent);
456 for (Relation sub : parent.getMemberPrimitives(Relation.class)) {
457 if (sub.isUsable() && !sub.isIncomplete()) {
458 checkLoop(sub, new LinkedList<>(path));
459 }
460 }
461 }
462
463 /**
464 * Check if adding one relation to another would produce a circular dependency.
465 * @param parent the relation which would be changed
466 * @param child the child relation which should be added to parent
467 * @return An unmodifiable list of relations which is empty when no circular dependency was found,
468 * else it contains the relations that form circular dependencies.
469 * The list then contains at least two items. Normally first and last item are both {@code parent},
470 * but if child is already part of a circular dependency the returned list may not end with {@code parent}.
471 */
472 public static List<Relation> checkAddMember(Relation parent, Relation child) {
473 if (parent == null || child == null)
474 return Collections.emptyList();
475 RelationChecker test = new RelationChecker();
476 LinkedList<Relation> path = new LinkedList<>();
477 path.add(parent);
478 test.checkLoop(child, path);
479 if (Boolean.TRUE.equals(ALLOW_COMPLEX_LOOP.get())) {
480 test.loops.removeIf(loop -> loop.size() > 2);
481 }
482 if (test.loops.isEmpty())
483 return Collections.emptyList();
484 else
485 return Collections.unmodifiableList(test.loops.iterator().next());
486 }
487
488}
Note: See TracBrowser for help on using the repository browser.