[core][tile mode] Fix placement order of the variable labels

Before this change, all variable labels that could potentially
intersect tile borders were placed first, breaking the style
label placement priority order.

2 files changed, 41 insertions, 29 deletions

diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index 7bf360a746..18e1123b32 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -239,7 +239,9 @@ void Placement::placeSymbolBucket(const BucketPlacementData& params, std::set<ui
                          collisionGroups.get(params.sourceId),
                          getAvoidEdges(symbolBucket, renderTile.matrix)};
     for (const SymbolInstance& symbol : getSortedSymbols(params, ctx.pixelRatio)) {
-        placeSymbol(symbol, ctx, seenCrossTileIDs);
+        if (seenCrossTileIDs.count(symbol.crossTileID) != 0u) continue;
+        placeSymbol(symbol, ctx);
+        seenCrossTileIDs.insert(symbol.crossTileID);
     }
 
     // As long as this placement lives, we have to hold onto this bucket's
@@ -250,18 +252,14 @@ void Placement::placeSymbolBucket(const BucketPlacementData& params, std::set<ui
         std::forward_as_tuple(symbolBucket.bucketInstanceId, params.featureIndex, ctx.getOverscaledID()));
 }
 
-void Placement::placeSymbol(const SymbolInstance& symbolInstance,
-                            const PlacementContext& ctx,
-                            std::set<uint32_t>& seenCrossTileIDs) {
-    if (symbolInstance.crossTileID == SymbolInstance::invalidCrossTileID() ||
-        seenCrossTileIDs.count(symbolInstance.crossTileID) != 0u)
-        return;
+JointPlacement Placement::placeSymbol(const SymbolInstance& symbolInstance, const PlacementContext& ctx) {
+    static const JointPlacement kUnplaced(false, false, false);
+    if (symbolInstance.crossTileID == SymbolInstance::invalidCrossTileID()) return kUnplaced;
 
     if (ctx.getRenderTile().holdForFade()) {
         // Mark all symbols from this tile as "not placed", but don't add to seenCrossTileIDs, because we don't
         // know yet if we have a duplicate in a parent tile that _should_ be placed.
-        placements.emplace(symbolInstance.crossTileID, JointPlacement(false, false, false));
-        return;
+        return kUnplaced;
     }
     const SymbolBucket& bucket = ctx.getBucket();
     const mat4& posMatrix = ctx.getRenderTile().matrix;
@@ -603,13 +601,11 @@ void Placement::placeSymbol(const SymbolInstance& symbolInstance,
         placements.erase(symbolInstance.crossTileID);
     }
 
-    auto pair = placements.emplace(
-        symbolInstance.crossTileID,
-        JointPlacement(
-            placeText || ctx.alwaysShowText, placeIcon || ctx.alwaysShowIcon, offscreen || bucket.justReloaded));
-    assert(pair.second);
-    newSymbolPlaced(symbolInstance, ctx, pair.first->second, ctx.placementType, textBoxes, iconBoxes);
-    seenCrossTileIDs.insert(symbolInstance.crossTileID);
+    JointPlacement result(
+        placeText || ctx.alwaysShowText, placeIcon || ctx.alwaysShowIcon, offscreen || bucket.justReloaded);
+    placements.emplace(symbolInstance.crossTileID, result);
+    newSymbolPlaced(symbolInstance, ctx, result, ctx.placementType, textBoxes, iconBoxes);
+    return result;
 }
 
 namespace {
@@ -1274,7 +1270,8 @@ private:
                          style::SymbolPlacementType,
                          const std::vector<ProjectedCollisionBox>&,
                          const std::vector<ProjectedCollisionBox>&) override;
-    void populateIntersectingSymbols();
+
+    bool shouldRetryPlacement(const JointPlacement&, const PlacementContext&);
 
     std::unordered_map<uint32_t, bool> locationCache;
     optional<CollisionBoundaries> tileBorders;
@@ -1297,7 +1294,7 @@ void TilePlacement::placeLayers(const RenderLayerReferences& layers) {
         placeLayer(*it, seenCrossTileIDs);
     }
 
-    std::stable_sort(intersections.begin(), intersections.end(), [](const Intersection& a, const Intersection& b) {
+    std::sort(intersections.begin(), intersections.end(), [](const Intersection& a, const Intersection& b) {
         if (a.priority != b.priority) return a.priority < b.priority;
         uint8_t flagsA = a.status.flags;
         uint8_t flagsB = b.status.flags;
@@ -1320,7 +1317,14 @@ void TilePlacement::placeLayers(const RenderLayerReferences& layers) {
     });
     // Place intersections.
     for (const auto& intersection : intersections) {
-        placeSymbol(intersection.symbol, intersection.ctx, seenCrossTileIDs);
+        const SymbolInstance& symbol = intersection.symbol;
+        const PlacementContext& ctx = intersection.ctx;
+        if (seenCrossTileIDs.count(symbol.crossTileID) != 0u) continue;
+        JointPlacement placement = placeSymbol(symbol, ctx);
+        if (shouldRetryPlacement(placement, ctx)) {
+            continue;
+        }
+        seenCrossTileIDs.insert(symbol.crossTileID);
     }
     // Place the rest labels.
     populateIntersections = false;
@@ -1473,13 +1477,17 @@ bool TilePlacement::canPlaceAtVariableAnchor(const CollisionBox& box,
                                              const mat4& posMatrix,
                                              float textPixelRatio) {
     assert(tileBorders);
+    if (populateIntersections) {
+        // A variable label is only allowed to intersect tile border with the first anchor.
+        if (anchor != anchors.front()) return false;
+        // Check, that the label would intersect the tile borders even without shift, otherwise intersection
+        // is not allowed (preventing cut-offs in case the shift is lager than the buffer size).
+        auto status = collisionIndex.intersectsTileEdges(box, {}, posMatrix, textPixelRatio, *tileBorders);
+        return status.flags != IntersectStatus::None;
+    }
+    // Can be placed, if it does not intersect tile borders.
     auto status = collisionIndex.intersectsTileEdges(box, shift, posMatrix, textPixelRatio, *tileBorders);
-    if (status.flags == IntersectStatus::None) return true;
-
-    if (anchor != anchors.front()) return false;
-
-    status = collisionIndex.intersectsTileEdges(box, {}, posMatrix, textPixelRatio, *tileBorders);
-    return status.flags != IntersectStatus::None;
+    return (status.flags == IntersectStatus::None);
 }
 
 void TilePlacement::newSymbolPlaced(const SymbolInstance& symbol,
@@ -1488,7 +1496,8 @@ void TilePlacement::newSymbolPlaced(const SymbolInstance& symbol,
                                     style::SymbolPlacementType placementType,
                                     const std::vector<ProjectedCollisionBox>& textCollisionBoxes,
                                     const std::vector<ProjectedCollisionBox>& iconCollisionBoxes) {
-    if (!collectData || placementType != style::SymbolPlacementType::Point) return;
+    if (!collectData || placementType != style::SymbolPlacementType::Point || shouldRetryPlacement(placement, ctx))
+        return;
 
     optional<mapbox::geometry::box<float>> textCollisionBox;
     if (!textCollisionBoxes.empty()) {
@@ -1515,6 +1524,11 @@ void TilePlacement::newSymbolPlaced(const SymbolInstance& symbol,
     placedSymbolsData.emplace_back(std::move(symbolData));
 }
 
+bool TilePlacement::shouldRetryPlacement(const JointPlacement& placement, const PlacementContext& ctx) {
+    // We re-try the placement to try out remaining variable anchors.
+    return populateIntersections && !placement.placed() && !ctx.getVariableTextAnchors().empty();
+}
+
 // static
 Mutable<Placement> Placement::create(std::shared_ptr<const UpdateParameters> updateParameters_,
                                      optional<Immutable<Placement>> prevPlacement) {
diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp
index f530b6c5f7..82a62718a4 100644
--- a/src/mbgl/text/placement.hpp
+++ b/src/mbgl/text/placement.hpp
@@ -142,9 +142,7 @@ public:
 protected:
     friend SymbolBucket;
     virtual void placeSymbolBucket(const BucketPlacementData&, std::set<uint32_t>& seenCrossTileIDs);
-    void placeSymbol(const SymbolInstance& symbolInstance,
-                     const PlacementContext&,
-                     std::set<uint32_t>& seenCrossTileIDs);
+    JointPlacement placeSymbol(const SymbolInstance& symbolInstance, const PlacementContext&);
     void placeLayer(const RenderLayer&, std::set<uint32_t>&);
     virtual void commit();
     virtual void newSymbolPlaced(const SymbolInstance&,