Changeset 16651 in josm

Timestamp:

2020-06-16T10:27:46+02:00 (4 years ago)

Author:

GerdP

Message:

fix #19312: detect circular dependencies in relations

• add test in RelationChecker to detect them
• show popup when user is about to create one and refuse the action

I am not happy with the texts but such a rather complex problem probably requires a complex message :(

Location:

trunk/src/org/openstreetmap/josm

Files:

• data/validation/tests/RelationChecker.java (modified) (8 diffs)
• gui/dialogs/relation/GenericRelationEditor.java (modified) (3 diffs)
• gui/dialogs/relation/actions/AddFromSelectionAction.java (modified) (2 diffs)

trunk/src/org/openstreetmap/josm/data/validation/tests/RelationChecker.java

@@ -7 +7 @@
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.EnumSet;
 import java.util.HashMap;
+import java.util.Iterator;
 import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
@@ -15 +18 @@
 import java.util.stream.Collectors;
 
+import org.openstreetmap.josm.command.ChangeCommand;
 import org.openstreetmap.josm.command.Command;
 import org.openstreetmap.josm.command.DeleteCommand;
@@ -62 +66 @@
     /** Type ''{0}'' of relation member with role ''{1}'' does not match accepted types ''{2}'' in preset {3} */
     public static final int WRONG_TYPE       = 1709;
+    /** Relations build circular dependencies */
+    public static final int RELATION_LOOP    = 1710;
     // CHECKSTYLE.ON: SingleSpaceSeparator
 
@@ -71 +77 @@
     private boolean ignoreMultiPolygons;
     private boolean ignoreTurnRestrictions;
-
+    private final List<List<Relation>> loops = new ArrayList<>();
     /**
      * Constructor
@@ -155 +161 @@
             checkRoles(n, allroles, map);
         }
+        checkLoop(n);
     }
 
@@ -370 +377 @@
         Collection<? extends OsmPrimitive> primitives = testError.getPrimitives();
         if (isFixable(testError) && !primitives.iterator().next().isDeleted()) {
-            return new DeleteCommand(primitives);
+            if (testError.getCode() == RELATION_EMPTY) {
+                return new DeleteCommand(primitives);
+            }
+            if (testError.getCode() == RELATION_LOOP) {
+                Relation old = (Relation) primitives.iterator().next();
+                Relation mod = new Relation(old);
+                mod.removeMembersFor(primitives);
+                return new ChangeCommand(old, mod);
+            }
         }
         return null;
@@ -378 +393 @@
     public boolean isFixable(TestError testError) {
         Collection<? extends OsmPrimitive> primitives = testError.getPrimitives();
-        return testError.getCode() == RELATION_EMPTY && !primitives.isEmpty() && primitives.iterator().next().isNew();
+        return (testError.getCode() == RELATION_EMPTY && !primitives.isEmpty() && primitives.iterator().next().isNew())
+                || (testError.getCode() == RELATION_LOOP && primitives.size() == 1);
     }
 
@@ -386 +402 @@
         initializePresets();
     }
+
+    @Override
+    public void endTest() {
+        loops.forEach(loop -> errors.add(TestError.builder(this, Severity.ERROR, RELATION_LOOP)
+                .message(loop.size() == 2 ? tr("Relation contains itself as a member")
+                        : tr("Relations generate circular dependency of parent/child elements"))
+                .primitives(new LinkedHashSet<>(loop))
+                .build()));
+        loops.clear();
+        super.endTest();
+    }
+
+    /**
+     * Check if a given relation is part of a circular dependency loop.
+     * @param r the relation
+     */
+    private void checkLoop(Relation r) {
+        checkLoop(r, new LinkedList<>());
+    }
+
+    private void checkLoop(Relation parent, List<Relation> path) {
+        if (path.contains(parent)) {
+            Iterator<List<Relation>> iter = loops.iterator();
+            while (iter.hasNext()) {
+                List<Relation> loop = iter.next();
+                if (loop.size() > path.size() && loop.containsAll(path)) {
+                    // remove same loop with irrelevant parent
+                    iter.remove();
+                } else if (path.size() >= loop.size() && path.containsAll(loop)) {
+                    // same or smaller loop is already known
+                    return;
+                }
+            }
+            if (path.get(0).equals(parent)) {
+                path.add(parent);
+                loops.add(path);
+            }
+            return;
+        }
+        path.add(parent);
+        for (Relation sub : parent.getMemberPrimitives(Relation.class)) {
+            if (sub.isUsable() && !sub.isIncomplete()) {
+                checkLoop(sub, new LinkedList<>(path));
+            }
+        }
+    }
+
+    /**
+     * Check if adding one relation to another would produce a circular dependency.
+     * @param parent the relation which would be changed
+     * @param child the child relation which should be added to parent
+     * @return An unmodifiable list of relations which is empty when no circular dependency was found,
+     * else it contains the relations that form circular dependencies.
+     * The list then contains at least two items. Normally first and last item are both {@code parent},
+     * but if child is already part of a circular dependency the returned list may not end with {@code parent}.
+     */
+    public static List<Relation> checkAddMember(Relation parent, Relation child) {
+        if (parent == null || child == null || child.isIncomplete())
+            return Collections.emptyList();
+        RelationChecker test = new RelationChecker();
+        LinkedList<Relation> path = new LinkedList<>();
+        path.add(parent);
+        test.checkLoop(child, path);
+        if (test.loops.isEmpty())
+            return Collections.emptyList();
+        else
+            return Collections.unmodifiableList(test.loops.iterator().next());
+    }
+
 }

trunk/src/org/openstreetmap/josm/gui/dialogs/relation/GenericRelationEditor.java

@@ -56 +56 @@
 import org.openstreetmap.josm.data.osm.RelationMember;
 import org.openstreetmap.josm.data.osm.Tag;
+import org.openstreetmap.josm.data.validation.tests.RelationChecker;
 import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
 import org.openstreetmap.josm.gui.MainApplication;
@@ -885 +886 @@
      */
     public static void warnOfCircularReferences(OsmPrimitive primitive) {
-        String msg = tr("<html>You are trying to add a relation to itself.<br>"
-                + "<br>"
-                + "This creates circular references and is therefore discouraged.<br>"
-                + "Skipping relation ''{0}''.</html>",
-                Utils.escapeReservedCharactersHTML(primitive.getDisplayName(DefaultNameFormatter.getInstance())));
+        warnOfCircularReferences(primitive, Collections.emptyList());
+    }
+
+    /**
+     * Warn about circular references.
+     * @param primitive the concerned primitive
+     * @param loop list of relation that form the circular dependencies.
+     *   Only used to report the loop if more than one relation is involved.
+     * @since 16651
+     */
+    public static void warnOfCircularReferences(OsmPrimitive primitive, List<Relation> loop) {
+        final String msg;
+        DefaultNameFormatter df = DefaultNameFormatter.getInstance();
+        if (loop.size() <= 2) {
+            msg = tr("<html>You are trying to add a relation to itself.<br>"
+                    + "<br>"
+                    + "This generates a circular dependency of parent/child elements and is therefore discouraged.<br>"
+                    + "Skipping relation ''{0}''.</html>",
+                    Utils.escapeReservedCharactersHTML(primitive.getDisplayName(df)));
+        } else {
+            msg = tr("<html>You are trying to add a child relation which refers to the parent relation.<br>"
+                    + "<br>"
+                    + "This generates a circular dependency of parent/child elements and is therefore discouraged.<br>"
+                    + "Skipping relation ''{0}''." + "<br>"
+                    + "Relations that would generate the circular dependency:<br>{1}</html>",
+                    Utils.escapeReservedCharactersHTML(primitive.getDisplayName(df)),
+                    loop.stream().map(p -> Utils.escapeReservedCharactersHTML(p.getDisplayName(df)))
+                            .collect(Collectors.joining(" -> <br>")));
+        }
         JOptionPane.showMessageDialog(
                 MainApplication.getMainFrame(),
@@ -912 +937 @@
             boolean modified = false;
             for (OsmPrimitive p : primitivesToAdd) {
-                if (p instanceof Relation && orig.equals(p)) {
-                    warnOfCircularReferences(p);
-                    continue;
+                if (p instanceof Relation) {
+                    List<Relation> loop = RelationChecker.checkAddMember(relation, (Relation) p);
+                    if (!loop.isEmpty() && loop.get(0).equals(loop.get(loop.size() - 1))) {
+                        warnOfCircularReferences(p, loop);
+                        continue;
+                    }
                 } else if (MemberTableModel.hasMembersReferringTo(relation.getMembers(), Collections.singleton(p))
                         && !confirmAddingPrimitive(p)) {

trunk/src/org/openstreetmap/josm/gui/dialogs/relation/actions/AddFromSelectionAction.java

@@ -8 +8 @@
 import org.openstreetmap.josm.data.osm.OsmPrimitive;
 import org.openstreetmap.josm.data.osm.Relation;
+import org.openstreetmap.josm.data.validation.tests.RelationChecker;
 import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
 import org.openstreetmap.josm.gui.dialogs.relation.GenericRelationEditor;
@@ -34 +35 @@
         ConditionalOptionPaneUtil.startBulkOperation("add_primitive_to_relation");
         for (OsmPrimitive primitive : primitives) {
-            if (primitive instanceof Relation
-                    && editorAccess.getEditor().getRelation() != null && editorAccess.getEditor().getRelation().equals(primitive)) {
-                GenericRelationEditor.warnOfCircularReferences(primitive);
-                continue;
+            if (primitive instanceof Relation) {
+                List<Relation> loop = RelationChecker.checkAddMember(editorAccess.getEditor().getRelation(), (Relation) primitive);
+                if (!loop.isEmpty() && loop.get(0).equals(loop.get(loop.size() - 1))) {
+                    GenericRelationEditor.warnOfCircularReferences(primitive, loop);
+                    continue;
+                }
             }
             if (isPotentialDuplicate(primitive)) {