Skip to content

Commit

Permalink
Fixing Way Section Exceeding Limit Bug (#203)
Browse files Browse the repository at this point in the history 
* Adding Ice Road Tag

* Adding public access tag value

* Reproducing the issue in old and new flow

* Adding boundary files for tests

* Renaming method to stay consistent

* Removing relations, they're not needed for the point of the test

* Updating tests, relations do matter, minor simplification in code

* Fixing way sectioning exceeding limit bug

* Reducing test atlas to bare minimum to reproduce issue
  • Loading branch information
@MikeGost @matthieun
MikeGost authored and matthieun committed Aug 27, 2018
1 parent 85caca6 commit a0c995b
Show file tree
Hide file tree
Showing 5 changed files with 2,106 additions and 25 deletions.
93 changes: 68 additions & 25 deletions ...main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -37,13 +37,14 @@
import org.openstreetmap.atlas.geography.sharding.Sharding;
import org.openstreetmap.atlas.tags.AtlasTag;
import org.openstreetmap.atlas.tags.LayerTag;
import org.openstreetmap.atlas.tags.SyntheticInvalidWaySectionTag;
import org.openstreetmap.atlas.utilities.collections.Iterables;
import org.openstreetmap.atlas.utilities.scalars.Distance;
import org.openstreetmap.atlas.utilities.scalars.Duration;
import org.openstreetmap.atlas.utilities.time.Time;
import org.openstreetmap.osmosis.core.domain.v0_6.Node;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.slf4j.helpers.MessageFormatter;

/**
* Way-section processor that runs on raw atlases. Its main purpose is to split raw atlas points
Expand All @@ -64,10 +65,12 @@ public class WaySectionProcessor
private static final int MINIMUM_NUMBER_OF_SELF_INTERSECTIONS_FOR_A_NODE = 3;
private static final int MINIMUM_SHAPE_POINTS_TO_QUALIFY_AS_AREA = 3;
private static final int MINIMUM_POINTS_TO_QUALIFY_AS_A_LINE = 2;
private static final int SINGLE_SECTIONING_IDENTIFIER_REMAINING_DELTA = 998;

// Logging constants
private static final String STARTED_TASK_MESSAGE = "Started {} for Shard {}";
private static final String COMPLETED_TASK_MESSAGE = "Finished {} for Shard {} in {}";
private static final String SHARD_SPECIFIC_COMPLETED_TASK_MESSAGE = "While processing shard {}, finished {} for shard {} in {}";
private static final String WAY_SECTIONING_TASK = "Way-Sectioning";
private static final String ATLAS_FETCHING_TASK = "Atlas-Fetching";
private static final String SUB_ATLAS_CUTTING_TASK = "Sub-Atlas Cutting";
Expand All @@ -82,21 +85,22 @@ public class WaySectionProcessor

private final Atlas rawAtlas;
private final AtlasLoadingOption loadingOption;

private final List<Shard> loadedShards = new ArrayList<>();

// Bring in all points that are part of any line that will become an edge
private final Predicate<AtlasEntity> pointPredicate = entity -> entity instanceof Point
&& Iterables.stream(entity.getAtlas().linesContaining(((Point) entity).getLocation()))
.anyMatch(this::isAtlasEdge);

// Bring in all lines that will become edges
private final Predicate<AtlasEntity> linePredicate = entity -> entity instanceof Line
&& isAtlasEdge((Line) entity);

// TODO - we are pulling in all edges and their contained points in the shard. We can optimize
// this further by only considering the edges crossing the shard boundary and their intersecting
// edges to reduce the memory overhead on each slave.

// Bring in all lines that will become edges
private final Predicate<AtlasEntity> linePredicate = entity -> entity instanceof Line
&& isAtlasEdge((Line) entity);

// Dynamic expansion filter will be a combination of points and lines
private final Predicate<AtlasEntity> dynamicAtlasExpansionFilter = entity -> this.pointPredicate
.test(entity) || this.linePredicate.test(entity);
Expand Down Expand Up @@ -175,7 +179,8 @@ public Atlas run()
sectionEdges(changeSet);

final Atlas atlas = buildSectionedAtlas(changeSet);
logTaskCompletionAsInfo(WAY_SECTIONING_TASK, getShardOrAtlasName(), time.elapsedSince());
logTaskAsInfo(COMPLETED_TASK_MESSAGE, WAY_SECTIONING_TASK, getShardOrAtlasName(),
time.elapsedSince());

return cutSubAtlasForOriginalShard(atlas);
}
Expand All @@ -197,6 +202,8 @@ private void addPointToNodeList(final Location location,
.addNode(new TemporaryNode(point.getIdentifier(), point.getLocation())));
}

// TODO add statistics

/**
* Grabs the atlas for the initial shard, in its entirety. Then proceeds to expand out to
* surrounding shards if there are any edges bleeding over the shard bounds plus
Expand Down Expand Up @@ -227,16 +234,16 @@ private Atlas buildExpandedAtlas(final Shard initialShard, final Sharding shardi
{
final Time fetchTime = Time.now();
final Optional<Atlas> fetchedAtlas = rawAtlasFetcher.apply(initialShard);
logTaskCompletionAsTrace(ATLAS_FETCHING_TASK, getShardOrAtlasName(),
logTaskAsTrace(COMPLETED_TASK_MESSAGE, ATLAS_FETCHING_TASK, getShardOrAtlasName(),
fetchTime.elapsedSince());
return fetchedAtlas;
}
else
{
final Time fetchTime = Time.now();
final Optional<Atlas> possibleAtlas = rawAtlasFetcher.apply(shard);
logTaskCompletionAsTrace(ATLAS_FETCHING_TASK, getShardOrAtlasName(),
fetchTime.elapsedSince());
logTaskAsInfo(SHARD_SPECIFIC_COMPLETED_TASK_MESSAGE, getShardOrAtlasName(),
ATLAS_FETCHING_TASK, shard.getName(), fetchTime.elapsedSince());

if (possibleAtlas.isPresent())
{
Expand All @@ -245,8 +252,8 @@ private Atlas buildExpandedAtlas(final Shard initialShard, final Sharding shardi
final Time subAtlasTime = Time.now();
final Optional<Atlas> subAtlas = atlas
.subAtlas(this.dynamicAtlasExpansionFilter);
logTaskCompletionAsTrace(SUB_ATLAS_CUTTING_TASK, getShardOrAtlasName(),
subAtlasTime.elapsedSince());
logTaskAsInfo(SHARD_SPECIFIC_COMPLETED_TASK_MESSAGE, getShardOrAtlasName(),
SUB_ATLAS_CUTTING_TASK, shard.getName(), subAtlasTime.elapsedSince());
return subAtlas;
}
return Optional.empty();
Expand All @@ -262,13 +269,11 @@ private Atlas buildExpandedAtlas(final Shard initialShard, final Sharding shardi
final DynamicAtlas atlas = new DynamicAtlas(policy);
atlas.preemptiveLoad();

logTaskCompletionAsInfo(DYNAMIC_ATLAS_CREATION_TASK, getShardOrAtlasName(),
logTaskAsInfo(COMPLETED_TASK_MESSAGE, DYNAMIC_ATLAS_CREATION_TASK, getShardOrAtlasName(),
dynamicAtlasTime.elapsedSince());
return atlas;
}

// TODO add statistics

/**
* Final step of way-sectioning. Use the {@link WaySectionChangeSet} to build an {@link Atlas}
* that has all entities.
Expand Down Expand Up @@ -419,7 +424,7 @@ else if (builder.peek().line(memberIdentifier) != null)
}
});

logTaskCompletionAsInfo(SECTIONED_ATLAS_CREATION_TASK, getShardOrAtlasName(),
logTaskAsInfo(COMPLETED_TASK_MESSAGE, SECTIONED_ATLAS_CREATION_TASK, getShardOrAtlasName(),
buildTime.elapsedSince());
return builder.get();
}
Expand Down Expand Up @@ -474,6 +479,27 @@ private AtlasSize createAtlasSizeEstimate(final WaySectionChangeSet changeSet)
this.rawAtlas.numberOfRelations());
}

private void createEdgeFromRemainingPolyline(final Line line, final int startIndex,
final boolean isReversed, final boolean hasReverseEdge,
final WaySectionIdentifierFactory identifierFactory,
final List<TemporaryEdge> newEdgesForLine)
{
// If we have a single way-section identifier left to use, we're going to run out
// identifiers if we continue sectioning. At this point, take the rest of the
// un-sectioned polyline and add it as the 999th edge.
final PolyLine polyline = line.asPolyLine();
final PolyLine rawPolyLine = new PolyLine(polyline.truncate(startIndex, 0));
final PolyLine edgePolyLine = isReversed ? rawPolyLine.reversed() : rawPolyLine;
final long edgeIdentifier = identifierFactory.nextIdentifier();

// Update the tags to indicate this edge wasn't way-sectioned
final Map<String, String> tags = line.getTags();
tags.put(SyntheticInvalidWaySectionTag.KEY, SyntheticInvalidWaySectionTag.YES.toString());

// Add the edge
newEdgesForLine.add(new TemporaryEdge(edgeIdentifier, edgePolyLine, tags, hasReverseEdge));
}

/**
* Up to this point, we've constructed the {@link DynamicAtlas} and way-sectioned it. Since
* we're only responsible for returning an Atlas for the provided shard, we now need to cut a
Expand Down Expand Up @@ -522,7 +548,7 @@ private void distinguishPointsFromShapePoints(final WaySectionChangeSet changeSe
final Time time = logTaskStartedAsInfo(SHAPE_POINT_DETECTION_TASK, getShardOrAtlasName());
StreamSupport.stream(this.rawAtlas.points().spliterator(), true)
.filter(point -> isAtlasPoint(changeSet, point)).forEach(changeSet::recordPoint);
logTaskCompletionAsInfo(SHAPE_POINT_DETECTION_TASK, getShardOrAtlasName(),
logTaskAsInfo(COMPLETED_TASK_MESSAGE, SHAPE_POINT_DETECTION_TASK, getShardOrAtlasName(),
time.elapsedSince());
}

Expand Down Expand Up @@ -636,7 +662,7 @@ else if (isAtlasLine(line))
}
});

logTaskCompletionAsInfo(ATLAS_FEATURE_DETECTION_TASK, getShardOrAtlasName(),
logTaskAsInfo(COMPLETED_TASK_MESSAGE, ATLAS_FEATURE_DETECTION_TASK, getShardOrAtlasName(),
time.elapsedSince());
}

Expand Down Expand Up @@ -772,16 +798,14 @@ && isAtlasEdge(target) && target.asPolyLine().contains(location)))
});
}

private void logTaskCompletionAsInfo(final String taskName, final String shardName,
final Duration duration)
private void logTaskAsInfo(final String message, final Object... arguments)
{
logger.info(COMPLETED_TASK_MESSAGE, taskName, shardName, duration);
logger.info(MessageFormatter.arrayFormat(message, arguments).getMessage());
}

private void logTaskCompletionAsTrace(final String taskName, final String shardName,
final Duration duration)
private void logTaskAsTrace(final String message, final Object... arguments)
{
logger.trace(COMPLETED_TASK_MESSAGE, taskName, shardName, duration);
logger.trace(MessageFormatter.arrayFormat(message, arguments).getMessage());
}

private Time logTaskStartedAsInfo(final String taskname, final String shardName)
Expand Down Expand Up @@ -877,7 +901,7 @@ private void sectionEdges(final WaySectionChangeSet changeSet)
changeSet.createLineToEdgeMapping(line, edges);
});

logTaskCompletionAsInfo(EDGE_SECTIONING_TASK, getShardOrAtlasName(),
logTaskAsInfo(COMPLETED_TASK_MESSAGE, EDGE_SECTIONING_TASK, getShardOrAtlasName(),
sectionTime.elapsedSince());
}

Expand Down Expand Up @@ -956,6 +980,15 @@ private List<TemporaryEdge> splitNonRingLineIntoEdges(final WaySectionChangeSet
// We've already processed the starting node, so start with the first index
for (int index = 1; index < polyline.size(); index++)
{
// Handle the case of exceeding the sectioning limit
if (identifierFactory.getDelta() == SINGLE_SECTIONING_IDENTIFIER_REMAINING_DELTA)
{
// Add the remaining polyline as an edge and stop sectioning
createEdgeFromRemainingPolyline(line, startIndex, isReversed, hasReverseEdge,
identifierFactory, newEdgesForLine);
break;
}

// Check to see if this location is a node
endNode = nodesToSectionAt.getNode(polyline.get(index));
if (endNode.isPresent())
Expand Down Expand Up @@ -1034,7 +1067,7 @@ private List<TemporaryEdge> splitNonRingLineIntoEdges(final WaySectionChangeSet
* iterating through all the line shape points, trying to match each one to a
* {@link TemporaryNode} for this {@link Line}. If we find a match, then we create a
* corresponding {@link TemporaryEdge}, making sure to reverse the polyline if the original line
* was reversed and to note whether we need to create a corresponding reverse edge. This main
* was reversed and to note whether we need to create a corresponding reverse edge. The main
* difference between this and the non-ring split method is that this one looks specifically for
* rings and avoid splitting at the first polyline location, since it is not guaranteed to be a
* node.
Expand Down Expand Up @@ -1102,6 +1135,16 @@ private List<TemporaryEdge> splitRingLineIntoEdges(final WaySectionChangeSet cha
duplicateLocations.put(currentLocation, duplicateCount + 1);
}

// Handle the case of exceeding the sectioning limit
if (identifierFactory
.getDelta() == SINGLE_SECTIONING_IDENTIFIER_REMAINING_DELTA)
{
// Add the remaining polyline as an edge and stop sectioning
createEdgeFromRemainingPolyline(line, startIndex, isReversed,
hasReverseEdge, identifierFactory, newEdgesForLine);
break;
}

// Check to see if this location is a node
if (endNode.isPresent())
{
Expand Down
26 changes: 26 additions & 0 deletions src/main/java/org/openstreetmap/atlas/tags/SyntheticInvalidWaySectionTag.java
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,26 @@
package org.openstreetmap.atlas.tags;

import org.openstreetmap.atlas.tags.annotations.Tag;
import org.openstreetmap.atlas.tags.annotations.TagKey;
import org.openstreetmap.atlas.tags.annotations.validation.Validators;

/**
* Tag identifying an Atlas Edge that was the remnant of way-sectioning that exceeded the maximum
* 999 slices. As a result, this edge contains the rest of the un-sectioned OSM Way. This usually
* indicates a data error and is NOT an OSM tag.
*
* @author mgostintsev
*/
@Tag(synthetic = true)
public enum SyntheticInvalidWaySectionTag
{
YES;

@TagKey
public static final String KEY = "synthetic_invalid_way_section";

public static boolean isYes(final Taggable taggable)
{
return Validators.isOfType(taggable, SyntheticInvalidWaySectionTag.class, YES);
}
}
48 changes: 48 additions & 0 deletions .../java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessorTest.java
View file
Original file line number Diff line number Diff line change
@@ -1,14 +1,23 @@
package org.openstreetmap.atlas.geography.atlas.raw.sectioning;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Assert;
import org.junit.Rule;
import org.junit.Test;
import org.openstreetmap.atlas.geography.Location;
import org.openstreetmap.atlas.geography.MultiPolygon;
import org.openstreetmap.atlas.geography.Polygon;
import org.openstreetmap.atlas.geography.atlas.Atlas;
import org.openstreetmap.atlas.geography.atlas.pbf.AtlasLoadingOption;
import org.openstreetmap.atlas.geography.atlas.raw.slicing.LineAndPointSlicingTest;
import org.openstreetmap.atlas.geography.boundary.CountryBoundaryMap;
import org.openstreetmap.atlas.streaming.compression.Decompressor;
import org.openstreetmap.atlas.streaming.resource.InputStreamResource;
import org.openstreetmap.atlas.tags.SyntheticInvalidWaySectionTag;
import org.openstreetmap.atlas.utilities.collections.Iterables;

/**
Expand Down Expand Up @@ -290,4 +299,43 @@ public void testSimpleBiDirectionalLine()
Assert.assertEquals("single edge and its counter part", 2, finalAtlas.numberOfEdges());
Assert.assertEquals("Two nodes - one at the start and end", 2, finalAtlas.numberOfNodes());
}

@Test
public void testWayExceedingSectioningLimit()
{
// Based on https://www.openstreetmap.org/way/608903805 and
// https://www.openstreetmap.org/way/608901269. These are stacked, duplicated ways that
// extend for a long time, causing sectioning to occur more than the allowed 999 times
final Atlas slicedRawAtlas = this.setup.getWayExceedingSectioningLimitAtlas();

// Create a dummy country boundary map that contains these ways and call it Afghanistan
final Set<String> countries = new HashSet<>();
final String afghanistan = "AFG";
countries.add(afghanistan);
final Map<String, MultiPolygon> boundaries = new HashMap<>();
final Polygon fakePolygon = new Polygon(Location.forString("34.15102284294,66.22764518738"),
Location.forString("34.1515910819,66.53388908386"),
Location.forString("33.99802783162,66.53045585632"),
Location.forString("33.99632001003,66.22558525085"),
Location.forString("34.15102284294,66.22764518738"));
final MultiPolygon boundary = MultiPolygon.forPolygon(fakePolygon);
boundaries.put(afghanistan, boundary);
final CountryBoundaryMap countryBoundaryMap = CountryBoundaryMap
.fromBoundaryMap(boundaries);

final Atlas finalAtlas = new WaySectionProcessor(slicedRawAtlas,
AtlasLoadingOption.createOptionWithAllEnabled(countryBoundaryMap)).run();

// Verify maximum number of sections for each edge
Assert.assertEquals(999,
Iterables.size(finalAtlas.edges(edge -> edge.getOsmIdentifier() == 608901269)));
Assert.assertEquals(999,
Iterables.size(finalAtlas.edges(edge -> edge.getOsmIdentifier() == 608903805)));

// Verify tag presence
Assert.assertEquals(SyntheticInvalidWaySectionTag.YES.name(),
finalAtlas.edge(608901269000999L).tag(SyntheticInvalidWaySectionTag.KEY));
Assert.assertEquals(SyntheticInvalidWaySectionTag.YES.name(),
finalAtlas.edge(608903805000999L).tag(SyntheticInvalidWaySectionTag.KEY));
}
}
8 changes: 8 additions & 0 deletions ...a/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessorTestRule.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -56,6 +56,9 @@ public class WaySectionProcessorTestRule extends CoreTestRule
@TestAtlas(loadFromTextResource = "selfIntersectingLoop.atlas.txt")
private Atlas selfIntersectingLoop;

@TestAtlas(loadFromTextResource = "wayExceedingSectioningLimit.atlas.txt")
private Atlas wayExceedingSectioningLimit;

public Atlas getBidirectionalRingAtlas()
{
return this.bidirectioalRingAtlas;
Expand Down Expand Up @@ -130,4 +133,9 @@ public Atlas getSimpleBiDirectionalLineAtlas()
{
return this.simpleBiDirectionalLine;
}

public Atlas getWayExceedingSectioningLimitAtlas()
{
return this.wayExceedingSectioningLimit;
}
}
1,956 changes: 1,956 additions & 0 deletions .../openstreetmap/atlas/geography/atlas/raw/sectioning/wayExceedingSectioningLimit.atlas.txt
View file

Large diffs are not rendered by default.

0 comments on commit a0c995b

Please sign in to comment.