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