001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.validation.tests; 003 004import static org.openstreetmap.josm.tools.I18n.marktr; 005import static org.openstreetmap.josm.tools.I18n.tr; 006 007import java.util.ArrayList; 008import java.util.Collection; 009import java.util.Collections; 010import java.util.EnumSet; 011import java.util.HashMap; 012import java.util.Iterator; 013import java.util.LinkedHashMap; 014import java.util.LinkedHashSet; 015import java.util.LinkedList; 016import java.util.List; 017import java.util.Map; 018import java.util.stream.Collectors; 019 020import org.openstreetmap.josm.command.ChangeMembersCommand; 021import org.openstreetmap.josm.command.Command; 022import org.openstreetmap.josm.command.DeleteCommand; 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.preferences.BooleanProperty; 028import org.openstreetmap.josm.data.validation.OsmValidator; 029import org.openstreetmap.josm.data.validation.Severity; 030import org.openstreetmap.josm.data.validation.Test; 031import org.openstreetmap.josm.data.validation.TestError; 032import org.openstreetmap.josm.gui.progress.ProgressMonitor; 033import org.openstreetmap.josm.gui.tagging.presets.TaggingPreset; 034import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetItem; 035import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetListener; 036import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetType; 037import org.openstreetmap.josm.gui.tagging.presets.TaggingPresets; 038import org.openstreetmap.josm.gui.tagging.presets.items.KeyedItem; 039import org.openstreetmap.josm.gui.tagging.presets.items.Roles; 040import org.openstreetmap.josm.gui.tagging.presets.items.Roles.Role; 041import org.openstreetmap.josm.tools.SubclassFilteredCollection; 042import org.openstreetmap.josm.tools.Utils; 043 044/** 045 * Check for wrong relations. 046 * @since 3669 047 */ 048public class RelationChecker extends Test implements TaggingPresetListener { 049 050 // CHECKSTYLE.OFF: SingleSpaceSeparator 051 /** Role ''{0}'' is not among expected values ''{1}'' */ 052 public static final int ROLE_UNKNOWN = 1701; 053 /** Empty role found when expecting one of ''{0}'' */ 054 public static final int ROLE_EMPTY = 1702; 055 /** Role of relation member does not match template expression ''{0}'' in preset {1} */ 056 public static final int WRONG_ROLE = 1708; 057 /** Number of ''{0}'' roles too high ({1}) */ 058 public static final int HIGH_COUNT = 1704; 059 /** Number of ''{0}'' roles too low ({1}) */ 060 public static final int LOW_COUNT = 1705; 061 /** Role ''{0}'' missing */ 062 public static final int ROLE_MISSING = 1706; 063 /** Relation type is unknown */ 064 public static final int RELATION_UNKNOWN = 1707; 065 /** Relation is empty */ 066 public static final int RELATION_EMPTY = 1708; 067 /** Type ''{0}'' of relation member with role ''{1}'' does not match accepted types ''{2}'' in preset {3} */ 068 public static final int WRONG_TYPE = 1709; 069 /** Relations build circular dependencies */ 070 public static final int RELATION_LOOP = 1710; 071 // CHECKSTYLE.ON: SingleSpaceSeparator 072 073 // see 19312 comment:17 074 private static final BooleanProperty ALLOW_COMPLEX_LOOP = new BooleanProperty("validator.relation.allow.complex.dependency", false); 075 076 /** 077 * Error message used to group errors related to role problems. 078 * @since 6731 079 */ 080 public static final String ROLE_VERIF_PROBLEM_MSG = tr("Role verification problem"); 081 private boolean ignoreMultiPolygons; 082 private boolean ignoreTurnRestrictions; 083 private final List<List<Relation>> loops = new ArrayList<>(); 084 /** 085 * Constructor 086 */ 087 public RelationChecker() { 088 super(tr("Relation checker"), 089 tr("Checks for errors in relations.")); 090 } 091 092 @Override 093 public void initialize() { 094 TaggingPresets.addListener(this); 095 initializePresets(); 096 } 097 098 private static final Collection<TaggingPreset> relationpresets = new LinkedList<>(); 099 100 /** 101 * Reads the presets data. 102 */ 103 public static synchronized void initializePresets() { 104 if (!relationpresets.isEmpty()) { 105 // the presets have already been initialized 106 return; 107 } 108 for (TaggingPreset p : TaggingPresets.getTaggingPresets()) { 109 if (p.data.stream().anyMatch(i -> i instanceof Roles)) { 110 relationpresets.add(p); 111 } 112 } 113 } 114 115 private static class RoleInfo { 116 private int total; 117 } 118 119 @Override 120 public void startTest(ProgressMonitor progressMonitor) { 121 super.startTest(progressMonitor); 122 123 for (Test t : OsmValidator.getEnabledTests(false)) { 124 if (t instanceof MultipolygonTest) { 125 ignoreMultiPolygons = true; 126 } 127 if (t instanceof TurnrestrictionTest) { 128 ignoreTurnRestrictions = true; 129 } 130 } 131 } 132 133 @Override 134 public void visit(Relation n) { 135 Map<String, RoleInfo> map = buildRoleInfoMap(n); 136 if (map.isEmpty()) { 137 errors.add(TestError.builder(this, Severity.ERROR, RELATION_EMPTY) 138 .message(tr("Relation is empty")) 139 .primitives(n) 140 .build()); 141 } 142 if (ignoreMultiPolygons && n.isMultipolygon()) { 143 // see #17010: don't report same problem twice 144 return; 145 } 146 if (ignoreTurnRestrictions && n.hasTag("type", "restriction")) { 147 // see #17561: don't report same problem twice 148 return; 149 } 150 Map<Role, String> allroles = buildAllRoles(n); 151 if (allroles.isEmpty() && n.hasTag("type", "route") 152 && n.hasTag("route", "train", "subway", "monorail", "tram", "bus", "trolleybus", "aerialway", "ferry")) { 153 errors.add(TestError.builder(this, Severity.WARNING, RELATION_UNKNOWN) 154 .message(tr("Route scheme is unspecified. Add {0} ({1}=public_transport; {2}=legacy)", "public_transport:version", "2", "1")) 155 .primitives(n) 156 .build()); 157 } else if (n.hasKey("type") && allroles.isEmpty()) { 158 errors.add(TestError.builder(this, Severity.OTHER, RELATION_UNKNOWN) 159 .message(tr("Relation type is unknown")) 160 .primitives(n) 161 .build()); 162 } 163 164 if (!map.isEmpty() && !allroles.isEmpty()) { 165 checkRoles(n, allroles, map); 166 } 167 checkLoop(n); 168 } 169 170 private static Map<String, RoleInfo> buildRoleInfoMap(Relation n) { 171 Map<String, RoleInfo> map = new HashMap<>(); 172 for (RelationMember m : n.getMembers()) { 173 map.computeIfAbsent(m.getRole(), k -> new RoleInfo()).total++; 174 } 175 return map; 176 } 177 178 // return Roles grouped by key 179 private static Map<Role, String> buildAllRoles(Relation n) { 180 Map<Role, String> allroles = new LinkedHashMap<>(); 181 182 for (TaggingPreset p : relationpresets) { 183 final boolean matches = TaggingPresetItem.matches(Utils.filteredCollection(p.data, KeyedItem.class), n.getKeys()); 184 final SubclassFilteredCollection<TaggingPresetItem, Roles> roles = Utils.filteredCollection(p.data, Roles.class); 185 if (matches && !roles.isEmpty()) { 186 for (Role role: roles.iterator().next().roles) { 187 allroles.put(role, p.name); 188 } 189 } 190 } 191 return allroles; 192 } 193 194 private static boolean checkMemberType(Role r, RelationMember member) { 195 if (r.types != null) { 196 switch (member.getDisplayType()) { 197 case NODE: 198 return r.types.contains(TaggingPresetType.NODE); 199 case CLOSEDWAY: 200 return r.types.contains(TaggingPresetType.CLOSEDWAY); 201 case WAY: 202 return r.types.contains(TaggingPresetType.WAY); 203 case MULTIPOLYGON: 204 return r.types.contains(TaggingPresetType.MULTIPOLYGON); 205 case RELATION: 206 return r.types.contains(TaggingPresetType.RELATION); 207 default: // not matching type 208 return false; 209 } 210 } else { 211 // if no types specified, then test is passed 212 return true; 213 } 214 } 215 216 /** 217 * get all role definition for specified key and check, if some definition matches 218 * 219 * @param allroles containing list of possible role presets of the member 220 * @param member to be verified 221 * @param n relation to be verified 222 * @return <code>true</code> if member passed any of definition within preset 223 * 224 */ 225 private boolean checkMemberExpressionAndType(Map<Role, String> allroles, RelationMember member, Relation n) { 226 String role = member.getRole(); 227 String name = null; 228 // Set of all accepted types in preset 229 Collection<TaggingPresetType> types = EnumSet.noneOf(TaggingPresetType.class); 230 TestError possibleMatchError = null; 231 // iterate through all of the role definition within preset 232 // and look for any matching definition 233 for (Map.Entry<Role, String> e : allroles.entrySet()) { 234 Role r = e.getKey(); 235 if (!r.isRole(role)) { 236 continue; 237 } 238 name = e.getValue(); 239 types.addAll(r.types); 240 if (checkMemberType(r, member)) { 241 // member type accepted by role definition 242 if (r.memberExpression == null) { 243 // no member expression - so all requirements met 244 return true; 245 } else { 246 // verify if preset accepts such member 247 OsmPrimitive primitive = member.getMember(); 248 if (!primitive.isUsable()) { 249 // if member is not usable (i.e. not present in working set) 250 // we can't verify expression - so we just skip it 251 return true; 252 } else { 253 // verify expression 254 if (r.memberExpression.match(primitive)) { 255 return true; 256 } else { 257 // possible match error 258 // we still need to iterate further, as we might have 259 // different preset, for which memberExpression will match 260 // but stash the error in case no better reason will be found later 261 possibleMatchError = TestError.builder(this, Severity.WARNING, WRONG_ROLE) 262 .message(ROLE_VERIF_PROBLEM_MSG, 263 marktr("Role of relation member does not match template expression ''{0}'' in preset {1}"), 264 r.memberExpression, name) 265 .primitives(member.getMember().isUsable() ? member.getMember() : n) 266 .build(); 267 } 268 } 269 } 270 } else if (OsmPrimitiveType.RELATION == member.getType() && !member.getMember().isUsable() 271 && r.types.contains(TaggingPresetType.MULTIPOLYGON)) { 272 // if relation is incomplete we cannot verify if it's a multipolygon - so we just skip it 273 return true; 274 } 275 } 276 277 if (name == null) { 278 return true; 279 } else if (possibleMatchError != null) { 280 // if any error found, then assume that member type was correct 281 // and complain about not matching the memberExpression 282 // (the only failure, that we could gather) 283 errors.add(possibleMatchError); 284 } else { 285 // no errors found till now. So member at least failed at matching the type 286 // it could also fail at memberExpression, but we can't guess at which 287 288 // Do not raise an error for incomplete ways for which we expect them to be closed, as we cannot know 289 boolean ignored = member.getMember().isIncomplete() && OsmPrimitiveType.WAY == member.getType() 290 && !types.contains(TaggingPresetType.WAY) && types.contains(TaggingPresetType.CLOSEDWAY); 291 if (!ignored) { 292 // convert in localization friendly way to string of accepted types 293 String typesStr = types.stream().map(x -> tr(x.getName())).collect(Collectors.joining("/")); 294 295 errors.add(TestError.builder(this, Severity.WARNING, WRONG_TYPE) 296 .message(ROLE_VERIF_PROBLEM_MSG, 297 marktr("Type ''{0}'' of relation member with role ''{1}'' does not match accepted types ''{2}'' in preset {3}"), 298 member.getType(), member.getRole(), typesStr, name) 299 .primitives(member.getMember().isUsable() ? member.getMember() : n) 300 .build()); 301 } 302 } 303 return false; 304 } 305 306 /** 307 * 308 * @param n relation to validate 309 * @param allroles contains presets for specified relation 310 * @param map contains statistics of occurrences of specified role in relation 311 */ 312 private void checkRoles(Relation n, Map<Role, String> allroles, Map<String, RoleInfo> map) { 313 // go through all members of relation 314 for (RelationMember member: n.getMembers()) { 315 // error reporting done inside 316 checkMemberExpressionAndType(allroles, member, n); 317 } 318 319 // verify role counts based on whole role sets 320 for (Role r: allroles.keySet()) { 321 String keyname = r.key; 322 if (keyname.isEmpty()) { 323 keyname = tr("<empty>"); 324 } 325 checkRoleCounts(n, r, keyname, map.get(r.key)); 326 } 327 if ("network".equals(n.get("type")) && !"bicycle".equals(n.get("route"))) { 328 return; 329 } 330 // verify unwanted members 331 for (String key : map.keySet()) { 332 if (allroles.keySet().stream().noneMatch(role -> role.isRole(key))) { 333 String templates = allroles.keySet().stream() 334 .map(r -> r.key) 335 .map(r -> Utils.isEmpty(r) ? tr("<empty>") : r) 336 .distinct() 337 .collect(Collectors.joining("/")); 338 List<OsmPrimitive> primitives = new ArrayList<>(n.findRelationMembers(key)); 339 primitives.add(0, n); 340 341 if (!key.isEmpty()) { 342 errors.add(TestError.builder(this, Severity.WARNING, ROLE_UNKNOWN) 343 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Role ''{0}'' is not among expected values ''{1}''"), key, templates) 344 .primitives(primitives) 345 .build()); 346 } else { 347 errors.add(TestError.builder(this, Severity.WARNING, ROLE_EMPTY) 348 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Empty role found when expecting one of ''{0}''"), templates) 349 .primitives(primitives) 350 .build()); 351 } 352 } 353 } 354 } 355 356 private void checkRoleCounts(Relation n, Role r, String keyname, RoleInfo ri) { 357 long count = (ri == null) ? 0 : ri.total; 358 long vc = r.getValidCount(count); 359 if (count != vc) { 360 if (count == 0) { 361 errors.add(TestError.builder(this, Severity.WARNING, ROLE_MISSING) 362 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Role ''{0}'' missing"), keyname) 363 .primitives(n) 364 .build()); 365 } else if (vc > count) { 366 errors.add(TestError.builder(this, Severity.WARNING, LOW_COUNT) 367 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Number of ''{0}'' roles too low ({1})"), keyname, count) 368 .primitives(n) 369 .build()); 370 } else { 371 errors.add(TestError.builder(this, Severity.WARNING, HIGH_COUNT) 372 .message(ROLE_VERIF_PROBLEM_MSG, marktr("Number of ''{0}'' roles too high ({1})"), keyname, count) 373 .primitives(n) 374 .build()); 375 } 376 } 377 } 378 379 @Override 380 public Command fixError(TestError testError) { 381 Collection<? extends OsmPrimitive> primitives = testError.getPrimitives(); 382 if (isFixable(testError) && !primitives.iterator().next().isDeleted()) { 383 if (testError.getCode() == RELATION_EMPTY) { 384 return new DeleteCommand(primitives); 385 } 386 if (testError.getCode() == RELATION_LOOP) { 387 Relation old = (Relation) primitives.iterator().next(); 388 List<RelationMember> remaining = new ArrayList<>(old.getMembers()); 389 remaining.removeIf(rm -> primitives.contains(rm.getMember())); 390 return new ChangeMembersCommand(old, Utils.toUnmodifiableList(remaining)); 391 } 392 } 393 return null; 394 } 395 396 @Override 397 public boolean isFixable(TestError testError) { 398 Collection<? extends OsmPrimitive> primitives = testError.getPrimitives(); 399 return (testError.getCode() == RELATION_EMPTY && !primitives.isEmpty() && primitives.iterator().next().isNew()) 400 || (testError.getCode() == RELATION_LOOP && primitives.size() == 1); 401 } 402 403 @Override 404 public void taggingPresetsModified() { 405 relationpresets.clear(); 406 initializePresets(); 407 } 408 409 @Override 410 public void endTest() { 411 if (Boolean.TRUE.equals(ALLOW_COMPLEX_LOOP.get())) { 412 loops.removeIf(loop -> loop.size() > 2); 413 } 414 loops.forEach(loop -> errors.add(TestError.builder(this, Severity.ERROR, RELATION_LOOP) 415 .message(loop.size() == 2 ? tr("Relation contains itself as a member") 416 : tr("Relations generate circular dependency of parent/child elements")) 417 .primitives(new LinkedHashSet<>(loop)) 418 .build())); 419 loops.clear(); 420 super.endTest(); 421 } 422 423 /** 424 * Check if a given relation is part of a circular dependency loop. 425 * @param r the relation 426 */ 427 private void checkLoop(Relation r) { 428 checkLoop(r, new LinkedList<>()); 429 } 430 431 private void checkLoop(Relation parent, List<Relation> path) { 432 if (path.contains(parent)) { 433 Iterator<List<Relation>> iter = loops.iterator(); 434 while (iter.hasNext()) { 435 List<Relation> loop = iter.next(); 436 if (loop.size() > path.size() && loop.containsAll(path)) { 437 // remove same loop with irrelevant parent 438 iter.remove(); 439 } else if (path.size() >= loop.size() && path.containsAll(loop)) { 440 // same or smaller loop is already known 441 return; 442 } 443 } 444 if (path.get(0).equals(parent)) { 445 path.add(parent); 446 loops.add(path); 447 } 448 return; 449 } 450 path.add(parent); 451 for (Relation sub : parent.getMemberPrimitives(Relation.class)) { 452 if (sub.isUsable() && !sub.isIncomplete()) { 453 checkLoop(sub, new LinkedList<>(path)); 454 } 455 } 456 } 457 458 /** 459 * Check if adding one relation to another would produce a circular dependency. 460 * @param parent the relation which would be changed 461 * @param child the child relation which should be added to parent 462 * @return An unmodifiable list of relations which is empty when no circular dependency was found, 463 * else it contains the relations that form circular dependencies. 464 * The list then contains at least two items. Normally first and last item are both {@code parent}, 465 * but if child is already part of a circular dependency the returned list may not end with {@code parent}. 466 */ 467 public static List<Relation> checkAddMember(Relation parent, Relation child) { 468 if (parent == null || child == null) 469 return Collections.emptyList(); 470 RelationChecker test = new RelationChecker(); 471 LinkedList<Relation> path = new LinkedList<>(); 472 path.add(parent); 473 test.checkLoop(child, path); 474 if (Boolean.TRUE.equals(ALLOW_COMPLEX_LOOP.get())) { 475 test.loops.removeIf(loop -> loop.size() > 2); 476 } 477 if (test.loops.isEmpty()) 478 return Collections.emptyList(); 479 else 480 return Collections.unmodifiableList(test.loops.iterator().next()); 481 } 482 483}