001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.validation.tests; 003 004import static org.openstreetmap.josm.tools.I18n.tr; 005import static org.openstreetmap.josm.tools.I18n.trn; 006 007import java.util.ArrayList; 008import java.util.Collection; 009import java.util.Collections; 010import java.util.Comparator; 011import java.util.HashMap; 012import java.util.List; 013import java.util.Map; 014import java.util.Map.Entry; 015import java.util.Set; 016import java.util.regex.Pattern; 017 018import org.openstreetmap.josm.data.osm.Node; 019import org.openstreetmap.josm.data.osm.OsmPrimitive; 020import org.openstreetmap.josm.data.osm.OsmPrimitiveType; 021import org.openstreetmap.josm.data.osm.Relation; 022import org.openstreetmap.josm.data.osm.RelationMember; 023import org.openstreetmap.josm.data.osm.Way; 024import org.openstreetmap.josm.data.validation.Severity; 025import org.openstreetmap.josm.data.validation.Test; 026import org.openstreetmap.josm.data.validation.TestError; 027import org.openstreetmap.josm.tools.Logging; 028import org.openstreetmap.josm.tools.Utils; 029 030/** 031 * Check for inconsistencies in lane information between relation and members. 032 */ 033public class ConnectivityRelations extends Test { 034 035 protected static final int INCONSISTENT_LANE_COUNT = 3900; 036 037 protected static final int UNKNOWN_CONNECTIVITY_ROLE = 3901; 038 039 protected static final int NO_CONNECTIVITY_TAG = 3902; 040 041 protected static final int MALFORMED_CONNECTIVITY_TAG = 3903; 042 043 protected static final int MISSING_COMMA_CONNECTIVITY_TAG = 3904; 044 045 protected static final int TOO_MANY_ROLES = 3905; 046 047 protected static final int MISSING_ROLE = 3906; 048 049 protected static final int MEMBER_MISSING_LANES = 3907; 050 051 protected static final int CONNECTIVITY_IMPLIED = 3908; 052 053 private static final String CONNECTIVITY_TAG = "connectivity"; 054 private static final String VIA = "via"; 055 private static final String TO = "to"; 056 private static final String FROM = "from"; 057 private static final int BW = -1000; 058 private static final Pattern OPTIONAL_LANE_PATTERN = Pattern.compile("\\([0-9-]+\\)"); 059 private static final Pattern TO_LANE_PATTERN = Pattern.compile("\\p{Zs}*[,:;]\\p{Zs}*"); 060 private static final Pattern MISSING_COMMA_PATTERN = Pattern.compile("[0-9]+\\([0-9]+\\)|\\([0-9]+\\)[0-9]+"); 061 private static final Pattern LANE_TAG_PATTERN = Pattern.compile(".*:lanes"); 062 063 /** 064 * Constructor 065 */ 066 public ConnectivityRelations() { 067 super(tr("Connectivity Relations"), tr("Validates connectivity relations")); 068 } 069 070 /** 071 * Convert the connectivity tag into a map of values 072 * 073 * @param relation A relation with a {@code connectivity} tag. 074 * @return A Map in the form of {@code Map<Lane From, Map<Lane To, Optional>>} May contain nulls when errors are encountered, 075 * empty collection if {@code connectivity} tag contains unusual values 076 */ 077 public static Map<Integer, Map<Integer, Boolean>> parseConnectivityTag(Relation relation) { 078 final String cnTag = relation.get(CONNECTIVITY_TAG); 079 if (Utils.isEmpty(cnTag)) { 080 return Collections.emptyMap(); 081 } 082 final String joined = cnTag.replace("bw", Integer.toString(BW)); 083 084 final Map<Integer, Map<Integer, Boolean>> result = new HashMap<>(); 085 String[] lanePairs = joined.split("\\|", -1); 086 for (final String lanePair : lanePairs) { 087 final String[] lane = lanePair.split(":", -1); 088 if (lane.length < 2) 089 return Collections.emptyMap(); 090 int laneNumber; 091 try { 092 laneNumber = Integer.parseInt(lane[0].trim()); 093 } catch (NumberFormatException e) { 094 return Collections.emptyMap(); 095 } 096 097 Map<Integer, Boolean> connections = new HashMap<>(); 098 String[] toLanes = TO_LANE_PATTERN.split(lane[1], -1); 099 for (String toLane : toLanes) { 100 try { 101 if (OPTIONAL_LANE_PATTERN.matcher(toLane).matches()) { 102 toLane = toLane.replace("(", "").replace(")", "").trim(); 103 connections.put(Integer.parseInt(toLane), Boolean.TRUE); 104 } else { 105 connections.put(Integer.parseInt(toLane), Boolean.FALSE); 106 } 107 } catch (NumberFormatException e) { 108 if (MISSING_COMMA_PATTERN.matcher(toLane).matches()) { 109 connections.put(null, Boolean.TRUE); 110 } else { 111 connections.put(null, null); 112 } 113 } 114 } 115 result.put(laneNumber, connections); 116 } 117 return Collections.unmodifiableMap(result); 118 } 119 120 @Override 121 public void visit(Relation r) { 122 if (r.hasTag("type", CONNECTIVITY_TAG)) { 123 if (!r.hasKey(CONNECTIVITY_TAG)) { 124 errors.add(TestError.builder(this, Severity.WARNING, NO_CONNECTIVITY_TAG) 125 .message(tr("Connectivity relation without connectivity tag")).primitives(r).build()); 126 } else if (!r.hasIncompleteMembers()) { 127 Map<Integer, Map<Integer, Boolean>> connTagLanes = parseConnectivityTag(r); 128 if (connTagLanes.isEmpty()) { 129 errors.add(TestError.builder(this, Severity.ERROR, MALFORMED_CONNECTIVITY_TAG) 130 .message(tr("Connectivity tag contains unusual data")).primitives(r).build()); 131 } else { 132 boolean badRole = checkForBadRole(r); 133 boolean missingRole = checkForMissingRole(r); 134 if (!badRole && !missingRole) { 135 Map<String, Integer> roleLanes = checkForInconsistentLanes(r, connTagLanes); 136 checkForImpliedConnectivity(r, roleLanes, connTagLanes); 137 } 138 } 139 } 140 } 141 } 142 143 /** 144 * Compare lane tags of members to values in the {@code connectivity} tag of the relation 145 * 146 * @param relation A relation with a {@code connectivity} tag. 147 * @param connTagLanes result of {@link ConnectivityRelations#parseConnectivityTag(Relation)} 148 * @return A Map in the form of {@code Map<Role, Lane Count>} 149 */ 150 private Map<String, Integer> checkForInconsistentLanes(Relation relation, Map<Integer, Map<Integer, Boolean>> connTagLanes) { 151 StringBuilder lanelessRoles = new StringBuilder(); 152 int lanelessRolesCount = 0; 153 // Lane count from connectivity tag 154 Map<String, Integer> roleLanes = new HashMap<>(); 155 if (connTagLanes.isEmpty()) 156 return roleLanes; 157 158 // If the ways involved in the connectivity tag are assuming a standard 2-way bi-directional highway 159 boolean defaultLanes = true; 160 for (Entry<Integer, Map<Integer, Boolean>> thisEntry : connTagLanes.entrySet()) { 161 for (Entry<Integer, Boolean> thisEntry2 : thisEntry.getValue().entrySet()) { 162 Logging.debug("Checking: " + thisEntry2.toString()); 163 if (thisEntry2.getKey() != null && thisEntry2.getKey() > 1) { 164 defaultLanes = false; 165 break; 166 } 167 } 168 if (!defaultLanes) { 169 break; 170 } 171 } 172 // Lane count from member tags 173 for (RelationMember rM : relation.getMembers()) { 174 // Check lanes 175 if (rM.getType() == OsmPrimitiveType.WAY) { 176 OsmPrimitive prim = rM.getMember(); 177 if (!VIA.equals(rM.getRole())) { 178 Map<String, String> primKeys = prim.getKeys(); 179 List<Long> laneCounts = new ArrayList<>(); 180 long maxLaneCount; 181 if (prim.hasTag("lanes")) { 182 laneCounts.add(Long.parseLong(prim.get("lanes"))); 183 } 184 for (Entry<String, String> entry : primKeys.entrySet()) { 185 String thisKey = entry.getKey(); 186 String thisValue = entry.getValue(); 187 if (LANE_TAG_PATTERN.matcher(thisKey).matches()) { 188 //Count bar characters 189 long count = thisValue.chars().filter(ch -> ch == '|').count() + 1; 190 laneCounts.add(count); 191 } 192 } 193 194 if (!laneCounts.isEmpty()) { 195 maxLaneCount = Collections.max(laneCounts); 196 roleLanes.put(rM.getRole(), (int) maxLaneCount); 197 } else { 198 if (lanelessRoles.length() > 0) { 199 lanelessRoles.append(" and "); 200 } 201 lanelessRoles.append('\'').append(rM.getRole()).append('\''); 202 lanelessRolesCount++; 203 } 204 } 205 } 206 } 207 208 if (lanelessRoles.length() == 0) { 209 boolean fromCheck = roleLanes.get(FROM) < Collections 210 .max(connTagLanes.entrySet(), Comparator.comparingInt(Map.Entry::getKey)).getKey(); 211 boolean toCheck = false; 212 for (Entry<Integer, Map<Integer, Boolean>> to : connTagLanes.entrySet()) { 213 if (!to.getValue().containsKey(null)) { 214 toCheck = roleLanes.get(TO) < Collections 215 .max(to.getValue().entrySet(), Comparator.comparingInt(Map.Entry::getKey)).getKey(); 216 } else { 217 if (to.getValue().containsValue(true)) { 218 errors.add(TestError.builder(this, Severity.ERROR, MISSING_COMMA_CONNECTIVITY_TAG) 219 .message(tr("Connectivity tag missing comma between optional and non-optional values")).primitives(relation) 220 .build()); 221 } else { 222 errors.add(TestError.builder(this, Severity.ERROR, MALFORMED_CONNECTIVITY_TAG) 223 .message(tr("Connectivity tag contains unusual data")).primitives(relation) 224 .build()); 225 } 226 } 227 } 228 if (fromCheck || toCheck) { 229 errors.add(TestError.builder(this, Severity.WARNING, INCONSISTENT_LANE_COUNT) 230 .message(tr("Inconsistent lane numbering between relation and member tags")).primitives(relation) 231 .build()); 232 } 233 } else if (!defaultLanes) { 234 errors.add(TestError.builder(this, Severity.WARNING, MEMBER_MISSING_LANES) 235 .message(trn("Relation {0} member is missing a lanes or *:lanes tag", 236 "Relation {0} members are missing a lanes or *:lanes tag", lanelessRolesCount, 237 lanelessRoles)) 238 .primitives(relation).build()); 239 } 240 return roleLanes; 241 } 242 243 /** 244 * Check the relation to see if the connectivity described is already implied by other data 245 * 246 * @param relation A relation with a {@code connectivity} tag. 247 * @param roleLanes The lane counts for each relation role 248 * @param connTagLanes result of {@link ConnectivityRelations#parseConnectivityTag(Relation)} 249 */ 250 private void checkForImpliedConnectivity(Relation relation, Map<String, Integer> roleLanes, 251 Map<Integer, Map<Integer, Boolean>> connTagLanes) { 252 // Don't flag connectivity as already implied when: 253 // - Lane counts are different on the roads 254 // - Placement tags convey the connectivity 255 // - The relation passes through an intersection 256 // - If via member is a node, it's connected to ways not in the relation 257 // - If a via member is a way, ways not in the relation connect to its nodes 258 // - Highways that appear to be merging have a different cumulative number of lanes than 259 // the highway that they're merging into 260 261 boolean connImplied = checkMemberTagsForImpliedConnectivity(relation, roleLanes) && !checkForIntersectionAtMembers(relation) 262 // Check if connectivity tag implies default connectivity 263 && connTagLanes.entrySet().stream() 264 .noneMatch(to -> { 265 int fromLane = to.getKey(); 266 return to.getValue().entrySet().stream() 267 .anyMatch(lane -> lane.getKey() != null && fromLane != lane.getKey()); 268 }); 269 270 if (connImplied) { 271 errors.add(TestError.builder(this, Severity.WARNING, CONNECTIVITY_IMPLIED) 272 .message(tr("This connectivity may already be implied")).primitives(relation) 273 .build()); 274 } 275 } 276 277 /** 278 * Check to see if there is an intersection present at the via member 279 * 280 * @param relation A relation with a {@code connectivity} tag. 281 * @return A Boolean that indicates whether an intersection is present at the via member 282 */ 283 private static boolean checkForIntersectionAtMembers(Relation relation) { 284 OsmPrimitive viaPrim = relation.findRelationMembers("via").get(0); 285 Set<OsmPrimitive> relationMembers = relation.getMemberPrimitives(); 286 287 if (viaPrim.getType() == OsmPrimitiveType.NODE) { 288 Node viaNode = (Node) viaPrim; 289 List<Way> parentWays = viaNode.getParentWays(); 290 if (parentWays.size() > 2) { 291 return parentWays.stream() 292 .anyMatch(thisWay -> !relationMembers.contains(thisWay) && thisWay.hasTag("highway")); 293 } 294 } else if (viaPrim.getType() == OsmPrimitiveType.WAY) { 295 Way viaWay = (Way) viaPrim; 296 return viaWay.getNodes().stream() 297 .map(Node::getParentWays).filter(parentWays -> parentWays.size() > 2) 298 .flatMap(Collection::stream) 299 .anyMatch(thisWay -> !relationMembers.contains(thisWay) && thisWay.hasTag("highway")); 300 } 301 return false; 302 } 303 304 /** 305 * Check the relation to see if the connectivity described is already implied by the relation members' tags 306 * 307 * @param relation A relation with a {@code connectivity} tag. 308 * @param roleLanes The lane counts for each relation role 309 * @return Whether connectivity is already implied by tags on relation members 310 */ 311 private static boolean checkMemberTagsForImpliedConnectivity(Relation relation, Map<String, Integer> roleLanes) { 312 // The members have different lane counts 313 if (roleLanes.containsKey(TO) && roleLanes.containsKey(FROM) && !roleLanes.get(TO).equals(roleLanes.get(FROM))) { 314 return false; 315 } 316 317 // The members don't have placement tags defining the connectivity 318 List<RelationMember> members = relation.getMembers(); 319 Map<String, OsmPrimitive> toFromMembers = new HashMap<>(); 320 for (RelationMember mem : members) { 321 if (mem.getRole().equals(FROM)) { 322 toFromMembers.put(FROM, mem.getMember()); 323 } else if (mem.getRole().equals(TO)) { 324 toFromMembers.put(TO, mem.getMember()); 325 } 326 } 327 328 return toFromMembers.get(TO).hasKey("placement") || toFromMembers.get(FROM).hasKey("placement"); 329 } 330 331 /** 332 * Check if the roles of the relation are appropriate 333 * 334 * @param relation A relation with a {@code connectivity} tag. 335 * @return Whether one or more of the relation's members has an unusual role 336 */ 337 private boolean checkForBadRole(Relation relation) { 338 // Check role names 339 int viaWays = 0; 340 int viaNodes = 0; 341 for (RelationMember relationMember : relation.getMembers()) { 342 if (relationMember.getMember() instanceof Way) { 343 if (relationMember.hasRole(VIA)) 344 viaWays++; 345 else if (!relationMember.hasRole(FROM) && !relationMember.hasRole(TO)) { 346 return true; 347 } 348 } else if (relationMember.getMember() instanceof Node) { 349 if (!relationMember.hasRole(VIA)) { 350 return true; 351 } 352 viaNodes++; 353 } 354 } 355 return mixedViaNodeAndWay(relation, viaWays, viaNodes); 356 } 357 358 /** 359 * Check if the relation contains all necessary roles 360 * 361 * @param relation A relation with a {@code connectivity} tag. 362 * @return Whether the relation is missing one or more of the critical {@code from}, {@code via}, or {@code to} roles 363 */ 364 private static boolean checkForMissingRole(Relation relation) { 365 List<String> necessaryRoles = new ArrayList<>(); 366 necessaryRoles.add(FROM); 367 necessaryRoles.add(VIA); 368 necessaryRoles.add(TO); 369 return !relation.getMemberRoles().containsAll(necessaryRoles); 370 } 371 372 /** 373 * Check if the relation's roles are on appropriate objects 374 * 375 * @param relation A relation with a {@code connectivity} tag. 376 * @param viaWays The number of ways in the relation with the {@code via} role 377 * @param viaNodes The number of nodes in the relation with the {@code via} role 378 * @return Whether the relation is missing one or more of the critical 'from', 'via', or 'to' roles 379 */ 380 private boolean mixedViaNodeAndWay(Relation relation, int viaWays, int viaNodes) { 381 String message = ""; 382 if (viaNodes > 1) { 383 if (viaWays > 0) { 384 message = tr("Relation should not contain mixed ''via'' ways and nodes"); 385 } else { 386 message = tr("Multiple ''via'' roles only allowed with ways"); 387 } 388 } 389 if (message.isEmpty()) { 390 return false; 391 } else { 392 errors.add(TestError.builder(this, Severity.WARNING, TOO_MANY_ROLES) 393 .message(message).primitives(relation).build()); 394 return true; 395 } 396 } 397 398}