001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.validation.tests;
003
004import static org.openstreetmap.josm.data.validation.tests.CrossingWays.HIGHWAY;
005import static org.openstreetmap.josm.data.validation.tests.CrossingWays.RAILWAY;
006import static org.openstreetmap.josm.data.validation.tests.CrossingWays.WATERWAY;
007import static org.openstreetmap.josm.tools.I18n.tr;
008
009import java.util.ArrayList;
010import java.util.Arrays;
011import java.util.Collection;
012import java.util.Collections;
013import java.util.HashMap;
014import java.util.HashSet;
015import java.util.LinkedHashSet;
016import java.util.List;
017import java.util.Map;
018import java.util.Set;
019import java.util.TreeSet;
020import java.util.function.Predicate;
021import java.util.stream.Collectors;
022
023import org.openstreetmap.josm.data.osm.IWaySegment;
024import org.openstreetmap.josm.data.osm.Node;
025import org.openstreetmap.josm.data.osm.OsmPrimitive;
026import org.openstreetmap.josm.data.osm.OsmUtils;
027import org.openstreetmap.josm.data.osm.Relation;
028import org.openstreetmap.josm.data.osm.Way;
029import org.openstreetmap.josm.data.osm.WaySegment;
030import org.openstreetmap.josm.data.preferences.ListProperty;
031import org.openstreetmap.josm.data.preferences.sources.ValidatorPrefHelper;
032import org.openstreetmap.josm.data.validation.Severity;
033import org.openstreetmap.josm.data.validation.Test;
034import org.openstreetmap.josm.data.validation.TestError;
035import org.openstreetmap.josm.gui.progress.ProgressMonitor;
036import org.openstreetmap.josm.spi.preferences.Config;
037import org.openstreetmap.josm.tools.MultiMap;
038import org.openstreetmap.josm.tools.Pair;
039
040/**
041 * Tests if there are overlapping ways.
042 *
043 * @author frsantos
044 * @since 3669
045 */
046public class OverlappingWays extends Test {
047
048    /** Bag of all way segments */
049    private MultiMap<Pair<Node, Node>, WaySegment> nodePairs;
050
051    private boolean onlyKnownLinear;
052    private boolean includeOther;
053    private boolean ignoreLayer;
054
055    protected static final int OVERLAPPING_HIGHWAY = 101;
056    protected static final int OVERLAPPING_RAILWAY = 102;
057    protected static final int OVERLAPPING_WAY = 103;
058    protected static final int OVERLAPPING_WATERWAY = 104;
059    protected static final int OVERLAPPING_HIGHWAY_AREA = 111;
060    protected static final int OVERLAPPING_RAILWAY_AREA = 112;
061    protected static final int OVERLAPPING_WAY_AREA = 113;
062    protected static final int OVERLAPPING_WATERWAY_AREA = 114;
063    protected static final int DUPLICATE_WAY_SEGMENT = 121;
064    protected static final int OVERLAPPING_HIGHWAY_LINEAR_WAY = 131;
065    protected static final int OVERLAPPING_RAILWAY_LINEAR_WAY = 132;
066    protected static final int OVERLAPPING_WATERWAY_LINEAR_WAY = 133;
067
068    protected static final ListProperty IGNORED_KEYS = new ListProperty(
069            "overlapping-ways.ignored-keys", Arrays.asList(
070                    "barrier", "indoor", "building", "building:part", "historic:building", "demolished:building",
071                    "removed:building", "disused:building", "abandoned:building", "proposed:building", "man_made"));
072    protected static final Predicate<OsmPrimitive> IGNORED = primitive ->
073            IGNORED_KEYS.get().stream().anyMatch(primitive::hasKey) || primitive.hasTag("tourism", "camp_site");
074
075    /** Constructor */
076    public OverlappingWays() {
077        super(tr("Overlapping ways"),
078                tr("This test checks that a connection between two nodes "
079                        + "is not used by more than one way."));
080    }
081
082    @Override
083    public void startTest(ProgressMonitor monitor) {
084        super.startTest(monitor);
085        nodePairs = new MultiMap<>(1000);
086        includeOther = isBeforeUpload ? ValidatorPrefHelper.PREF_OTHER_UPLOAD.get() : ValidatorPrefHelper.PREF_OTHER.get();
087        onlyKnownLinear = Config.getPref().getBoolean("overlapping-ways.only-known-linear", true);
088        ignoreLayer = Config.getPref().getBoolean("overlapping-ways.ignore-layer", false);
089    }
090
091    private static boolean parentMultipolygonConcernsArea(OsmPrimitive p) {
092        return p.referrers(Relation.class)
093                .anyMatch(Relation::isMultipolygon);
094    }
095
096    @Override
097    public void endTest() {
098        Map<List<Way>, Set<WaySegment>> seenWays = new HashMap<>(500);
099
100        for (Set<WaySegment> duplicated : nodePairs.values()) {
101            if (duplicated.size() <= 1)
102                continue;
103            if (ignoreLayer) {
104                analyseOverlaps(duplicated, seenWays);
105            } else {
106                // group by layer tag value (which is very likely null)
107                Map<String, Set<WaySegment>> grouped = new HashMap<>();
108                for (WaySegment ws : duplicated) {
109                    // order in set is important
110                    grouped.computeIfAbsent(OsmUtils.getLayer(ws.getWay()), k -> new LinkedHashSet<>()).add(ws);
111                }
112                grouped.values().forEach(group -> analyseOverlaps(group, seenWays));
113            }
114        }
115        nodePairs = null;
116
117        super.endTest();
118    }
119
120    private void analyseOverlaps(Set<WaySegment> duplicated, Map<List<Way>, Set<WaySegment>> seenWays) {
121        int ways = duplicated.size();
122        if (ways <= 1)
123            return;
124
125        List<Way> currentWays = duplicated.stream().map(IWaySegment::getWay).collect(Collectors.toList());
126        Collection<WaySegment> highlight;
127        if ((highlight = seenWays.get(currentWays)) != null) {
128            /* this combination of ways was seen before, just add highlighted segment */
129            highlight.addAll(duplicated);
130        } else {
131            int countHighway = 0;
132            int countRailway = 0;
133            int countWaterway = 0;
134            int countOther = 0;
135            int numAreas = 0;
136            for (WaySegment ws : duplicated) {
137                boolean isArea = ws.getWay().concernsArea();
138                if (ws.getWay().hasKey(HIGHWAY)) {
139                    if (!isArea) {
140                        countHighway++;
141                    }
142                } else if (ws.getWay().hasKey(RAILWAY)) {
143                    if (!isArea) {
144                        countRailway++;
145                    }
146                } else if (ws.getWay().hasKey(WATERWAY)) {
147                    if (!isArea) {
148                        countWaterway++;
149                    }
150                } else {
151                    if (ws.getWay().getInterestingTags().isEmpty() && parentMultipolygonConcernsArea(ws.getWay()))
152                        isArea = true;
153                    if (!isArea && isOtherLinear(ws.getWay())) {
154                        countOther++;
155                    }
156                }
157                if (isArea) {
158                    numAreas++;
159                }
160            }
161            if (numAreas == ways) {
162                // no linear object, we don't care when areas share segments
163                return;
164            }
165
166
167            // If two or more of the overlapping ways are highways or railways mark a separate error
168            String errortype;
169            int type;
170            int allKnownLinear = countHighway + countRailway + countWaterway + countOther;
171            final Severity severity;
172            if (countHighway > 1) {
173                errortype = tr("Overlapping highways");
174                type = OVERLAPPING_HIGHWAY;
175                severity = Severity.ERROR;
176            } else if (countRailway > 1) {
177                errortype = tr("Overlapping railways");
178                type = OVERLAPPING_RAILWAY;
179                severity = Severity.ERROR;
180            } else if (countWaterway > 1) {
181                errortype = tr("Overlapping waterways");
182                type = OVERLAPPING_WATERWAY;
183                severity = Severity.ERROR;
184            } else if (countHighway > 0 && countHighway < allKnownLinear) {
185                errortype = tr("Highway shares segment with linear way");
186                type = OVERLAPPING_HIGHWAY_LINEAR_WAY;
187                severity = Severity.WARNING;
188            } else if (countRailway > 0 && countRailway < allKnownLinear) {
189                errortype = tr("Railway shares segment with linear way");
190                type = OVERLAPPING_HIGHWAY_LINEAR_WAY;
191                severity = Severity.WARNING;
192            } else if (countWaterway > 0 && countWaterway < allKnownLinear) {
193                errortype = tr("Waterway shares segment with linear way");
194                type = OVERLAPPING_WATERWAY_LINEAR_WAY;
195                severity = Severity.WARNING;
196            } else if (!includeOther || onlyKnownLinear) {
197                return;
198            } else if (countHighway > 0) {
199                errortype = tr("Highway shares segment with other way");
200                type = OVERLAPPING_HIGHWAY_AREA;
201                severity = Severity.OTHER;
202            } else if (countRailway > 0) {
203                errortype = tr("Railway shares segment with other way");
204                type = OVERLAPPING_RAILWAY_AREA;
205                severity = Severity.OTHER;
206            } else if (countWaterway > 0) {
207                errortype = tr("Waterway shares segment with other way");
208                type = OVERLAPPING_WATERWAY_AREA;
209                severity = Severity.OTHER;
210            } else {
211                errortype = tr("Ways share segment");
212                type = OVERLAPPING_WAY;
213                severity = Severity.OTHER;
214            }
215
216            List<OsmPrimitive> prims = new ArrayList<>(currentWays);
217            errors.add(TestError.builder(this, severity, type)
218                    .message(errortype)
219                    .primitives(prims)
220                    .highlightWaySegments(duplicated)
221                    .build());
222            seenWays.put(currentWays, duplicated);
223        }
224    }
225
226    private static boolean isOtherLinear(Way way) {
227        // it is assumed that area=* was evaluated before and is false
228        return (way.hasKey("barrier", "addr:interpolation", "route", "ford")
229                || way.hasTag("natural", "tree_row", "cliff", "ridge")
230                || way.hasTag("power", "line", "minor_line", "cable", "portal")
231                || way.hasTag("man_made", "pipeline"));
232    }
233
234    protected static Set<WaySegment> checkDuplicateWaySegment(Way w) {
235        // test for ticket #4959
236        Set<WaySegment> segments = new TreeSet<>((o1, o2) -> {
237            final List<Node> n1 = Arrays.asList(o1.getFirstNode(), o1.getSecondNode());
238            final List<Node> n2 = Arrays.asList(o2.getFirstNode(), o2.getSecondNode());
239            Collections.sort(n1);
240            Collections.sort(n2);
241            final int first = n1.get(0).compareTo(n2.get(0));
242            final int second = n1.get(1).compareTo(n2.get(1));
243            return first != 0 ? first : second;
244        });
245        final Set<WaySegment> duplicateWaySegments = new HashSet<>();
246
247        for (int i = 0; i < w.getNodesCount() - 1; i++) {
248            final WaySegment segment = new WaySegment(w, i);
249            final boolean wasInSet = !segments.add(segment);
250            if (wasInSet) {
251                duplicateWaySegments.add(segment);
252            }
253        }
254        return duplicateWaySegments;
255    }
256
257    @Override
258    public void visit(Way w) {
259
260        final Set<WaySegment> duplicateWaySegment = checkDuplicateWaySegment(w);
261        if (!duplicateWaySegment.isEmpty()) {
262            errors.add(TestError.builder(this, Severity.ERROR, DUPLICATE_WAY_SEGMENT)
263                    .message(tr("Way contains segment twice"))
264                    .primitives(w)
265                    .highlightWaySegments(duplicateWaySegment)
266                    .build());
267            return;
268        }
269
270        if (IGNORED.test(w))
271            return;
272
273        if (onlyKnownLinear && (w.concernsArea() || w.getInterestingTags().isEmpty()))
274            return;
275
276        Node lastN = null;
277        int i = -2;
278        for (Node n : w.getNodes()) {
279            i++;
280            if (lastN == null) {
281                lastN = n;
282                continue;
283            }
284            nodePairs.put(Pair.sort(new Pair<>(lastN, n)),
285                    new WaySegment(w, i));
286            lastN = n;
287        }
288    }
289}