Changeset 16651 in josm


Ignore:
Timestamp:
2020-06-16T10:27:46+02:00 (7 weeks 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:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/data/validation/tests/RelationChecker.java

    r16616 r16651  
    77import java.util.ArrayList;
    88import java.util.Collection;
     9import java.util.Collections;
    910import java.util.EnumSet;
    1011import java.util.HashMap;
     12import java.util.Iterator;
    1113import java.util.LinkedHashMap;
     14import java.util.LinkedHashSet;
    1215import java.util.LinkedList;
    1316import java.util.List;
     
    1518import java.util.stream.Collectors;
    1619
     20import org.openstreetmap.josm.command.ChangeCommand;
    1721import org.openstreetmap.josm.command.Command;
    1822import org.openstreetmap.josm.command.DeleteCommand;
     
    6266    /** Type ''{0}'' of relation member with role ''{1}'' does not match accepted types ''{2}'' in preset {3} */
    6367    public static final int WRONG_TYPE       = 1709;
     68    /** Relations build circular dependencies */
     69    public static final int RELATION_LOOP    = 1710;
    6470    // CHECKSTYLE.ON: SingleSpaceSeparator
    6571
     
    7177    private boolean ignoreMultiPolygons;
    7278    private boolean ignoreTurnRestrictions;
    73 
     79    private final List<List<Relation>> loops = new ArrayList<>();
    7480    /**
    7581     * Constructor
     
    155161            checkRoles(n, allroles, map);
    156162        }
     163        checkLoop(n);
    157164    }
    158165
     
    370377        Collection<? extends OsmPrimitive> primitives = testError.getPrimitives();
    371378        if (isFixable(testError) && !primitives.iterator().next().isDeleted()) {
    372             return new DeleteCommand(primitives);
     379            if (testError.getCode() == RELATION_EMPTY) {
     380                return new DeleteCommand(primitives);
     381            }
     382            if (testError.getCode() == RELATION_LOOP) {
     383                Relation old = (Relation) primitives.iterator().next();
     384                Relation mod = new Relation(old);
     385                mod.removeMembersFor(primitives);
     386                return new ChangeCommand(old, mod);
     387            }
    373388        }
    374389        return null;
     
    378393    public boolean isFixable(TestError testError) {
    379394        Collection<? extends OsmPrimitive> primitives = testError.getPrimitives();
    380         return testError.getCode() == RELATION_EMPTY && !primitives.isEmpty() && primitives.iterator().next().isNew();
     395        return (testError.getCode() == RELATION_EMPTY && !primitives.isEmpty() && primitives.iterator().next().isNew())
     396                || (testError.getCode() == RELATION_LOOP && primitives.size() == 1);
    381397    }
    382398
     
    386402        initializePresets();
    387403    }
     404
     405    @Override
     406    public void endTest() {
     407        loops.forEach(loop -> errors.add(TestError.builder(this, Severity.ERROR, RELATION_LOOP)
     408                .message(loop.size() == 2 ? tr("Relation contains itself as a member")
     409                        : tr("Relations generate circular dependency of parent/child elements"))
     410                .primitives(new LinkedHashSet<>(loop))
     411                .build()));
     412        loops.clear();
     413        super.endTest();
     414    }
     415
     416    /**
     417     * Check if a given relation is part of a circular dependency loop.
     418     * @param r the relation
     419     */
     420    private void checkLoop(Relation r) {
     421        checkLoop(r, new LinkedList<>());
     422    }
     423
     424    private void checkLoop(Relation parent, List<Relation> path) {
     425        if (path.contains(parent)) {
     426            Iterator<List<Relation>> iter = loops.iterator();
     427            while (iter.hasNext()) {
     428                List<Relation> loop = iter.next();
     429                if (loop.size() > path.size() && loop.containsAll(path)) {
     430                    // remove same loop with irrelevant parent
     431                    iter.remove();
     432                } else if (path.size() >= loop.size() && path.containsAll(loop)) {
     433                    // same or smaller loop is already known
     434                    return;
     435                }
     436            }
     437            if (path.get(0).equals(parent)) {
     438                path.add(parent);
     439                loops.add(path);
     440            }
     441            return;
     442        }
     443        path.add(parent);
     444        for (Relation sub : parent.getMemberPrimitives(Relation.class)) {
     445            if (sub.isUsable() && !sub.isIncomplete()) {
     446                checkLoop(sub, new LinkedList<>(path));
     447            }
     448        }
     449    }
     450
     451    /**
     452     * Check if adding one relation to another would produce a circular dependency.
     453     * @param parent the relation which would be changed
     454     * @param child the child relation which should be added to parent
     455     * @return An unmodifiable list of relations which is empty when no circular dependency was found,
     456     * else it contains the relations that form circular dependencies.
     457     * The list then contains at least two items. Normally first and last item are both {@code parent},
     458     * but if child is already part of a circular dependency the returned list may not end with {@code parent}.
     459     */
     460    public static List<Relation> checkAddMember(Relation parent, Relation child) {
     461        if (parent == null || child == null || child.isIncomplete())
     462            return Collections.emptyList();
     463        RelationChecker test = new RelationChecker();
     464        LinkedList<Relation> path = new LinkedList<>();
     465        path.add(parent);
     466        test.checkLoop(child, path);
     467        if (test.loops.isEmpty())
     468            return Collections.emptyList();
     469        else
     470            return Collections.unmodifiableList(test.loops.iterator().next());
     471    }
     472
    388473}
  • trunk/src/org/openstreetmap/josm/gui/dialogs/relation/GenericRelationEditor.java

    r16438 r16651  
    5656import org.openstreetmap.josm.data.osm.RelationMember;
    5757import org.openstreetmap.josm.data.osm.Tag;
     58import org.openstreetmap.josm.data.validation.tests.RelationChecker;
    5859import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
    5960import org.openstreetmap.josm.gui.MainApplication;
     
    885886     */
    886887    public static void warnOfCircularReferences(OsmPrimitive primitive) {
    887         String msg = tr("<html>You are trying to add a relation to itself.<br>"
    888                 + "<br>"
    889                 + "This creates circular references and is therefore discouraged.<br>"
    890                 + "Skipping relation ''{0}''.</html>",
    891                 Utils.escapeReservedCharactersHTML(primitive.getDisplayName(DefaultNameFormatter.getInstance())));
     888        warnOfCircularReferences(primitive, Collections.emptyList());
     889    }
     890
     891    /**
     892     * Warn about circular references.
     893     * @param primitive the concerned primitive
     894     * @param loop list of relation that form the circular dependencies.
     895     *   Only used to report the loop if more than one relation is involved.
     896     * @since 16651
     897     */
     898    public static void warnOfCircularReferences(OsmPrimitive primitive, List<Relation> loop) {
     899        final String msg;
     900        DefaultNameFormatter df = DefaultNameFormatter.getInstance();
     901        if (loop.size() <= 2) {
     902            msg = tr("<html>You are trying to add a relation to itself.<br>"
     903                    + "<br>"
     904                    + "This generates a circular dependency of parent/child elements and is therefore discouraged.<br>"
     905                    + "Skipping relation ''{0}''.</html>",
     906                    Utils.escapeReservedCharactersHTML(primitive.getDisplayName(df)));
     907        } else {
     908            msg = tr("<html>You are trying to add a child relation which refers to the parent relation.<br>"
     909                    + "<br>"
     910                    + "This generates a circular dependency of parent/child elements and is therefore discouraged.<br>"
     911                    + "Skipping relation ''{0}''." + "<br>"
     912                    + "Relations that would generate the circular dependency:<br>{1}</html>",
     913                    Utils.escapeReservedCharactersHTML(primitive.getDisplayName(df)),
     914                    loop.stream().map(p -> Utils.escapeReservedCharactersHTML(p.getDisplayName(df)))
     915                            .collect(Collectors.joining(" -> <br>")));
     916        }
    892917        JOptionPane.showMessageDialog(
    893918                MainApplication.getMainFrame(),
     
    912937            boolean modified = false;
    913938            for (OsmPrimitive p : primitivesToAdd) {
    914                 if (p instanceof Relation && orig.equals(p)) {
    915                     warnOfCircularReferences(p);
    916                     continue;
     939                if (p instanceof Relation) {
     940                    List<Relation> loop = RelationChecker.checkAddMember(relation, (Relation) p);
     941                    if (!loop.isEmpty() && loop.get(0).equals(loop.get(loop.size() - 1))) {
     942                        warnOfCircularReferences(p, loop);
     943                        continue;
     944                    }
    917945                } else if (MemberTableModel.hasMembersReferringTo(relation.getMembers(), Collections.singleton(p))
    918946                        && !confirmAddingPrimitive(p)) {
  • trunk/src/org/openstreetmap/josm/gui/dialogs/relation/actions/AddFromSelectionAction.java

    r14030 r16651  
    88import org.openstreetmap.josm.data.osm.OsmPrimitive;
    99import org.openstreetmap.josm.data.osm.Relation;
     10import org.openstreetmap.josm.data.validation.tests.RelationChecker;
    1011import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
    1112import org.openstreetmap.josm.gui.dialogs.relation.GenericRelationEditor;
     
    3435        ConditionalOptionPaneUtil.startBulkOperation("add_primitive_to_relation");
    3536        for (OsmPrimitive primitive : primitives) {
    36             if (primitive instanceof Relation
    37                     && editorAccess.getEditor().getRelation() != null && editorAccess.getEditor().getRelation().equals(primitive)) {
    38                 GenericRelationEditor.warnOfCircularReferences(primitive);
    39                 continue;
     37            if (primitive instanceof Relation) {
     38                List<Relation> loop = RelationChecker.checkAddMember(editorAccess.getEditor().getRelation(), (Relation) primitive);
     39                if (!loop.isEmpty() && loop.get(0).equals(loop.get(loop.size() - 1))) {
     40                    GenericRelationEditor.warnOfCircularReferences(primitive, loop);
     41                    continue;
     42                }
    4043            }
    4144            if (isPotentialDuplicate(primitive)) {
Note: See TracChangeset for help on using the changeset viewer.