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}