[core] Prevent symbols at the same zoom from sharing a crossTileID.upstream/cloer-10844

Port of GL JS PR #5994.
Fixes issue #10844, which would allow multiple symbols in a tile to share the same crossTileID as one of their duplicate parent-tile symbols. Once the symbols shared a crossTileID, they would permanently remain "duplicates" of each other, even after increasing zoom level allowed the CrossTileSymbolIndex to distinguish between them.

3 files changed, 108 insertions, 9 deletions

diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp
index 30d265d885..a9210601f9 100644
--- a/src/mbgl/text/cross_tile_symbol_index.cpp
+++ b/src/mbgl/text/cross_tile_symbol_index.cpp
@@ -24,7 +24,7 @@ Point<int64_t> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstan
     };
 }
 
-void TileLayerIndex::findMatches(std::vector<SymbolInstance>& symbolInstances, const OverscaledTileID& newCoord) {
+void TileLayerIndex::findMatches(std::vector<SymbolInstance>& symbolInstances, const OverscaledTileID& newCoord, std::set<uint32_t>& zoomCrossTileIDs) {
     float tolerance = coord.canonical.z < newCoord.canonical.z ? 1 : std::pow(2, coord.canonical.z - newCoord.canonical.z);
 
     for (auto& symbolInstance : symbolInstances) {
@@ -45,8 +45,12 @@ void TileLayerIndex::findMatches(std::vector<SymbolInstance>& symbolInstances, c
             // Return any symbol with the same keys whose coordinates are within 1
             // grid unit. (with a 4px grid, this covers a 12px by 12px area)
             if (std::abs(thisTileSymbol.coord.x - scaledSymbolCoord.x) <= tolerance &&
-                std::abs(thisTileSymbol.coord.y - scaledSymbolCoord.y) <= tolerance) {
-
+                std::abs(thisTileSymbol.coord.y - scaledSymbolCoord.y) <= tolerance &&
+                zoomCrossTileIDs.find(thisTileSymbol.crossTileID) == zoomCrossTileIDs.end()) {
+                // Once we've marked ourselves duplicate against this parent symbol,
+                // don't let any other symbols at the same zoom level duplicate against
+                // the same parent (see issue #10844)
+                zoomCrossTileIDs.insert(thisTileSymbol.crossTileID);
                 symbolInstance.crossTileID = thisTileSymbol.crossTileID;
                 break;
             }
@@ -60,8 +64,15 @@ CrossTileSymbolLayerIndex::CrossTileSymbolLayerIndex() {
 bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, SymbolBucket& bucket, uint32_t& maxCrossTileID) {
     auto thisZoomIndexes = indexes[tileID.overscaledZ];
     auto previousIndex = thisZoomIndexes.find(tileID);
-    if (previousIndex != thisZoomIndexes.end() && previousIndex->second.bucketInstanceId == bucket.bucketInstanceId) {
-        return false;
+    if (previousIndex != thisZoomIndexes.end()) {
+        if (previousIndex->second.bucketInstanceId == bucket.bucketInstanceId) {
+            return false;
+        } else {
+            // We're replacing this bucket with an updated version
+            // Remove the old bucket's "used crossTileIDs" now so that the new bucket can claim them.
+            // The old index entries themselves stick around until 'removeStaleBuckets' is called.
+            removeBucketCrossTileIDs(tileID.overscaledZ, previousIndex->second);
+        }
     }
 
     for (auto& symbolInstance: bucket.symbolInstances) {
@@ -74,14 +85,14 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol
         if (zoom > tileID.overscaledZ) {
             for (auto& childIndex : zoomIndexes) {
                 if (childIndex.second.coord.isChildOf(tileID)) {
-                    childIndex.second.findMatches(bucket.symbolInstances, tileID);
+                    childIndex.second.findMatches(bucket.symbolInstances, tileID, usedCrossTileIDs[tileID.overscaledZ]);
                 }
             }
         } else {
             auto parentTileID = tileID.scaledTo(zoom);
             auto parentIndex = zoomIndexes.find(parentTileID);
             if (parentIndex != zoomIndexes.end()) {
-                parentIndex->second.findMatches(bucket.symbolInstances, tileID);
+                parentIndex->second.findMatches(bucket.symbolInstances, tileID, usedCrossTileIDs[tileID.overscaledZ]);
             }
         }
     }
@@ -90,6 +101,7 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol
         if (!symbolInstance.crossTileID) {
             // symbol did not match any known symbol, assign a new id
             symbolInstance.crossTileID = ++maxCrossTileID;
+            usedCrossTileIDs[tileID.overscaledZ].insert(symbolInstance.crossTileID);
         }
     }
 
@@ -99,11 +111,20 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol
     return true;
 }
 
+void CrossTileSymbolLayerIndex::removeBucketCrossTileIDs(uint8_t zoom, const TileLayerIndex& removedBucket) {
+    for (auto key : removedBucket.indexedSymbolInstances) {
+        for (auto indexedSymbolInstance : key.second) {
+            usedCrossTileIDs[zoom].erase(indexedSymbolInstance.crossTileID);
+        }
+    }
+}
+
 bool CrossTileSymbolLayerIndex::removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs) {
     bool tilesChanged = false;
     for (auto& zoomIndexes : indexes) {
         for (auto it = zoomIndexes.second.begin(); it != zoomIndexes.second.end();) {
             if (!currentIDs.count(it->second.bucketInstanceId)) {
+                removeBucketCrossTileIDs(zoomIndexes.first, it->second);
                 it = zoomIndexes.second.erase(it);
                 tilesChanged = true;
             } else {
diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp
index 995e0061b9..5abcde241c 100644
--- a/src/mbgl/text/cross_tile_symbol_index.hpp
+++ b/src/mbgl/text/cross_tile_symbol_index.hpp
@@ -6,6 +6,7 @@
 #include <mbgl/util/optional.hpp>
 
 #include <map>
+#include <set>
 #include <vector>
 #include <string>
 #include <memory>
@@ -32,7 +33,7 @@ public:
     TileLayerIndex(OverscaledTileID coord, std::vector<SymbolInstance>&, uint32_t bucketInstanceId);
 
     Point<int64_t> getScaledCoordinates(SymbolInstance&, const OverscaledTileID&);
-    void findMatches(std::vector<SymbolInstance>&, const OverscaledTileID&);
+    void findMatches(std::vector<SymbolInstance>&, const OverscaledTileID&, std::set<uint32_t>&);
     
     OverscaledTileID coord;
     uint32_t bucketInstanceId;
@@ -45,7 +46,10 @@ public:
     bool addBucket(const OverscaledTileID&, SymbolBucket&, uint32_t& maxCrossTileID);
     bool removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs);
 private:
-    std::map<uint8_t,std::map<OverscaledTileID,TileLayerIndex>> indexes;
+    void removeBucketCrossTileIDs(uint8_t zoom, const TileLayerIndex& removedBucket);
+
+    std::map<uint8_t, std::map<OverscaledTileID,TileLayerIndex>> indexes;
+    std::map<uint8_t, std::set<uint32_t>> usedCrossTileIDs;
 };
 
 class CrossTileSymbolIndex {
diff --git a/test/text/cross_tile_symbol_index.test.cpp b/test/text/cross_tile_symbol_index.test.cpp
index ef5bd4a101..794c2b59a1 100644
--- a/test/text/cross_tile_symbol_index.test.cpp
+++ b/test/text/cross_tile_symbol_index.test.cpp
@@ -127,3 +127,77 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
     index.addBucket(mainID, mainBucket, maxCrossTileID);
     ASSERT_EQ(mainBucket.symbolInstances.at(0).crossTileID, 2u);
 }
+
+TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
+    uint32_t maxCrossTileID = 0;
+    uint32_t maxBucketInstanceId = 0;
+    CrossTileSymbolLayerIndex index;
+
+    style::SymbolLayoutProperties::PossiblyEvaluated layout;
+    bool sdfIcons = false;
+    bool iconsNeedLinear = false;
+    bool sortFeaturesByY = false;
+
+    OverscaledTileID mainID(6, 0, 6, 8, 8);
+    std::vector<SymbolInstance> mainInstances;
+    mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A
+    mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B
+    SymbolBucket mainBucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(mainInstances) };
+    mainBucket.bucketInstanceId = ++maxBucketInstanceId;
+
+    OverscaledTileID childID(7, 0, 7, 16, 16);
+    std::vector<SymbolInstance> childInstances;
+    childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // A'
+    childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // B'
+    childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // C'
+    SymbolBucket childBucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(childInstances) };
+    childBucket.bucketInstanceId = ++maxBucketInstanceId;
+
+    // assigns new ids
+    index.addBucket(mainID, mainBucket, maxCrossTileID);
+    ASSERT_EQ(mainBucket.symbolInstances.at(0).crossTileID, 1u);
+    ASSERT_EQ(mainBucket.symbolInstances.at(1).crossTileID, 2u);
+
+    // copies parent ids without duplicate ids in this tile
+    index.addBucket(childID, childBucket, maxCrossTileID);
+    ASSERT_EQ(childBucket.symbolInstances.at(0).crossTileID, 1u); // A' copies from A
+    ASSERT_EQ(childBucket.symbolInstances.at(1).crossTileID, 2u); // B' copies from B
+    ASSERT_EQ(childBucket.symbolInstances.at(2).crossTileID, 3u); // C' gets new ID
+}
+
+TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
+    uint32_t maxCrossTileID = 0;
+    uint32_t maxBucketInstanceId = 0;
+    CrossTileSymbolLayerIndex index;
+
+    style::SymbolLayoutProperties::PossiblyEvaluated layout;
+    bool sdfIcons = false;
+    bool iconsNeedLinear = false;
+    bool sortFeaturesByY = false;
+
+    OverscaledTileID tileID(6, 0, 6, 8, 8);
+    std::vector<SymbolInstance> firstInstances;
+    firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A
+    firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B
+    SymbolBucket firstBucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(firstInstances) };
+    firstBucket.bucketInstanceId = ++maxBucketInstanceId;
+
+    std::vector<SymbolInstance> secondInstances;
+    secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A'
+    secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B'
+    secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // C'
+    SymbolBucket secondBucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(secondInstances) };
+    secondBucket.bucketInstanceId = ++maxBucketInstanceId;
+
+    // assigns new ids
+    index.addBucket(tileID, firstBucket, maxCrossTileID);
+    ASSERT_EQ(firstBucket.symbolInstances.at(0).crossTileID, 1u);
+    ASSERT_EQ(firstBucket.symbolInstances.at(1).crossTileID, 2u);
+
+    // copies parent ids without duplicate ids in this tile
+    index.addBucket(tileID, secondBucket, maxCrossTileID);
+    ASSERT_EQ(secondBucket.symbolInstances.at(0).crossTileID, 1u); // A' copies from A
+    ASSERT_EQ(secondBucket.symbolInstances.at(1).crossTileID, 2u); // B' copies from B
+    ASSERT_EQ(secondBucket.symbolInstances.at(2).crossTileID, 3u); // C' gets new ID
+}
+