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}