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.HashSet; 013import java.util.Iterator; 014import java.util.LinkedHashMap; 015import java.util.LinkedHashSet; 016import java.util.LinkedList; 017import java.util.List; 018import java.util.Map; 019import java.util.Set; 020import java.util.stream.Collectors; 021 022import org.openstreetmap.josm.command.ChangeMembersCommand; 023import org.openstreetmap.josm.command.Command; 024import org.openstreetmap.josm.command.DeleteCommand; 025import org.openstreetmap.josm.data.osm.OsmPrimitive; 026import org.openstreetmap.josm.data.osm.OsmPrimitiveType; 027import org.openstreetmap.josm.data.osm.Relation; 028import org.openstreetmap.josm.data.osm.RelationMember; 029import org.openstreetmap.josm.data.preferences.BooleanProperty; 030import org.openstreetmap.josm.data.validation.OsmValidator; 031import org.openstreetmap.josm.data.validation.Severity; 032import org.openstreetmap.josm.data.validation.Test; 033import org.openstreetmap.josm.data.validation.TestError; 034import org.openstreetmap.josm.gui.progress.ProgressMonitor; 035import org.openstreetmap.josm.gui.tagging.presets.TaggingPreset; 036import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetItem; 037import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetListener; 038import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetType; 039import org.openstreetmap.josm.gui.tagging.presets.TaggingPresets; 040import org.openstreetmap.josm.gui.tagging.presets.items.KeyedItem; 041import org.openstreetmap.josm.gui.tagging.presets.items.Roles; 042import org.openstreetmap.josm.gui.tagging.presets.items.Roles.Role; 043import org.openstreetmap.josm.tools.SubclassFilteredCollection; 044import org.openstreetmap.josm.tools.Utils; 045 046/** 047 * Check for wrong relations. 048 * @since 3669 049 */ 050public class RelationChecker extends Test implements TaggingPresetListener { 051 052 // CHECKSTYLE.OFF: SingleSpaceSeparator 053 /** Role ''{0}'' is not among expected values ''{1}'' */ 054 public static final int ROLE_UNKNOWN = 1701; 055 /** Empty role found when expecting one of ''{0}'' */ 056 public static final int ROLE_EMPTY = 1702; 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 /** Role of relation member does not match template expression ''{0}'' in preset {1} */ 066 public static final int WRONG_ROLE = 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 /** Relation is empty */ 072 public static final int RELATION_EMPTY = 1711; // was 1708 up to r18505 073 // CHECKSTYLE.ON: SingleSpaceSeparator 074 075 // see 19312 comment:17 076 private static final BooleanProperty ALLOW_COMPLEX_LOOP = new BooleanProperty("validator.relation.allow.complex.dependency", false); 077 078 /** 079 * Error message used to group errors related to role problems. 080 * @since 6731 081 */ 082 public static final String ROLE_VERIF_PROBLEM_MSG = tr("Role verification problem"); 083 private boolean ignoreMultiPolygons; 084 private boolean ignoreTurnRestrictions; 085 private final List<List<Relation>> loops = new ArrayList<>(); 086 /** 087 * Constructor 088 */ 089 public RelationChecker() { 090 super(tr("Relation checker"), 091 tr("Checks for errors in relations.")); 092 } 093 094 @Override 095 public void initialize() { 096 TaggingPresets.addListener(this); 097 initializePresets(); 098 } 099 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(Roles.class::isInstance)) { 112 relationpresets.add(p); 113 } 114 } 115 } 116 117 private static final 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}