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}