Quadkey tokens in tile URL templates, limited WMS support (#5628)

* [core] Quadkey tokens in tile URL templates

Fixes #5485.

* [core] WMS tokens in tile URL templates

Fixes #822.

* [macos] Added WMS debug style

Added a style to the macosapp resource bundle that can be used to test WMS support. To use it, zoom in to somewhere in New Jersey, then go to View ‣ Custom Style and enter “wms.json”.

6 files changed, 122 insertions, 0 deletions

diff --git a/platform/ios/CHANGELOG.md b/platform/ios/CHANGELOG.md
index f8c5f51616..db5265e64f 100644
--- a/platform/ios/CHANGELOG.md
+++ b/platform/ios/CHANGELOG.md
@@ -4,6 +4,8 @@ Mapbox welcomes participation and contributions from everyone.  Please read [CON
 
 ## master
 
+* Added [quadkey](https://msdn.microsoft.com/en-us/library/bb259689.aspx) support and limited WMS support in raster tile URL templates. ([#5628](https://github.com/mapbox/mapbox-gl-native/pull/5628))
+
 ## 3.3.0
 
 ### Styles and data
diff --git a/platform/macos/CHANGELOG.md b/platform/macos/CHANGELOG.md
index c30dbe064b..939706351b 100644
--- a/platform/macos/CHANGELOG.md
+++ b/platform/macos/CHANGELOG.md
@@ -5,6 +5,7 @@
 * Right-clicking to open MGLMapView’s context menu no longer prevents the user from subsequently panning the map by clicking and dragging. ([#5593](https://github.com/mapbox/mapbox-gl-native/pull/5593))
 * Replaced the wireframe debug mask with an overdraw visualization debug mask to match Mapbox GL JS’s overdraw inspector. ([#5403](https://github.com/mapbox/mapbox-gl-native/pull/5403))
 * Improved the design of the generated API documentation. ([#5306](https://github.com/mapbox/mapbox-gl-native/pull/5306))
+* Added [quadkey](https://msdn.microsoft.com/en-us/library/bb259689.aspx) support and limited WMS support in raster tile URL templates. ([#5628](https://github.com/mapbox/mapbox-gl-native/pull/5628))
 
 ## 0.2.0
 
diff --git a/platform/macos/app/wms.json b/platform/macos/app/wms.json
new file mode 100644
index 0000000000..e5fb236259
--- /dev/null
+++ b/platform/macos/app/wms.json
@@ -0,0 +1,21 @@
+{
+  "version": 8,
+  "name": "WMS Test",
+  "sources": {
+    "wms-test": {
+      "type": "raster",
+      "tiles": [
+        "https://geodata.state.nj.us/imagerywms/Natural2015?bbox={bbox-epsg-3857}&format=image/png&service=WMS&version=1.1.1&request=GetMap&srs=EPSG:3857&width=256&height=256&layers=Natural2015"
+      ],
+      "tileSize": 256
+    }
+  },
+  "layers": [{
+    "id": "wms-test-layer",
+    "type": "raster",
+    "source": "wms-test",
+    "paint": {
+      "raster-fade-duration": 100
+    }
+  }]
+}
diff --git a/platform/macos/macos.xcodeproj/project.pbxproj b/platform/macos/macos.xcodeproj/project.pbxproj
index 10f57a369a..4c2b75659c 100644
--- a/platform/macos/macos.xcodeproj/project.pbxproj
+++ b/platform/macos/macos.xcodeproj/project.pbxproj
@@ -20,6 +20,7 @@
 		DA35A2C21CCA9F4A00E826B2 /* MGLClockDirectionFormatterTests.m in Sources */ = {isa = PBXBuildFile; fileRef = DA35A2C11CCA9F4A00E826B2 /* MGLClockDirectionFormatterTests.m */; };
 		DA35A2CF1CCAAED300E826B2 /* NSValue+MGLAdditions.h in Headers */ = {isa = PBXBuildFile; fileRef = DA35A2CD1CCAAED300E826B2 /* NSValue+MGLAdditions.h */; settings = {ATTRIBUTES = (Public, ); }; };
 		DA35A2D01CCAAED300E826B2 /* NSValue+MGLAdditions.m in Sources */ = {isa = PBXBuildFile; fileRef = DA35A2CE1CCAAED300E826B2 /* NSValue+MGLAdditions.m */; };
+		DA5589771D320C41006B7F64 /* wms.json in Resources */ = {isa = PBXBuildFile; fileRef = DA5589761D320C41006B7F64 /* wms.json */; };
 		DA839E971CC2E3400062CAFB /* AppDelegate.m in Sources */ = {isa = PBXBuildFile; fileRef = DA839E961CC2E3400062CAFB /* AppDelegate.m */; };
 		DA839E9A1CC2E3400062CAFB /* main.m in Sources */ = {isa = PBXBuildFile; fileRef = DA839E991CC2E3400062CAFB /* main.m */; };
 		DA839E9D1CC2E3400062CAFB /* MapDocument.m in Sources */ = {isa = PBXBuildFile; fileRef = DA839E9C1CC2E3400062CAFB /* MapDocument.m */; };
@@ -159,6 +160,7 @@
 		DA35A2C11CCA9F4A00E826B2 /* MGLClockDirectionFormatterTests.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = MGLClockDirectionFormatterTests.m; path = ../../darwin/test/MGLClockDirectionFormatterTests.m; sourceTree = "<group>"; };
 		DA35A2CD1CCAAED300E826B2 /* NSValue+MGLAdditions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = "NSValue+MGLAdditions.h"; sourceTree = "<group>"; };
 		DA35A2CE1CCAAED300E826B2 /* NSValue+MGLAdditions.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = "NSValue+MGLAdditions.m"; sourceTree = "<group>"; };
+		DA5589761D320C41006B7F64 /* wms.json */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.json; path = wms.json; sourceTree = "<group>"; };
 		DA839E921CC2E3400062CAFB /* Mapbox GL.app */ = {isa = PBXFileReference; explicitFileType = wrapper.application; includeInIndex = 0; path = "Mapbox GL.app"; sourceTree = BUILT_PRODUCTS_DIR; };
 		DA839E951CC2E3400062CAFB /* AppDelegate.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = AppDelegate.h; sourceTree = "<group>"; };
 		DA839E961CC2E3400062CAFB /* AppDelegate.m */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.objc; path = AppDelegate.m; sourceTree = "<group>"; };
@@ -334,6 +336,7 @@
 				DAE6C2EC1CC3050F00DB3429 /* TimeIntervalTransformer.m */,
 				DA839EA11CC2E3400062CAFB /* Assets.xcassets */,
 				DA839EA31CC2E3400062CAFB /* MainMenu.xib */,
+				DA5589761D320C41006B7F64 /* wms.json */,
 				DAE6C2E11CC304F900DB3429 /* Credits.rtf */,
 				DA839EA61CC2E3400062CAFB /* Info.plist */,
 				DA839E981CC2E3400062CAFB /* Supporting Files */,
@@ -721,6 +724,7 @@
 				DA839EA21CC2E3400062CAFB /* Assets.xcassets in Resources */,
 				DA839EA01CC2E3400062CAFB /* MapDocument.xib in Resources */,
 				DA839EA51CC2E3400062CAFB /* MainMenu.xib in Resources */,
+				DA5589771D320C41006B7F64 /* wms.json in Resources */,
 				DAE6C2E21CC304F900DB3429 /* Credits.rtf in Resources */,
 			);
 			runOnlyForDeploymentPostprocessing = 0;
diff --git a/src/mbgl/storage/resource.cpp b/src/mbgl/storage/resource.cpp
index 8019e4aeb7..bb587dcc33 100644
--- a/src/mbgl/storage/resource.cpp
+++ b/src/mbgl/storage/resource.cpp
@@ -1,10 +1,44 @@
+#include <mapbox/geometry/box.hpp>
 #include <mbgl/storage/resource.hpp>
+#include <mbgl/util/constants.hpp>
 #include <mbgl/util/string.hpp>
 #include <mbgl/util/token.hpp>
 #include <mbgl/util/url.hpp>
 
+#include <cmath>
+
 namespace mbgl {
 
+static std::string getQuadKey(int32_t x, int32_t y, int8_t z) {
+    std::string quadKey;
+    quadKey.reserve(z);
+    int32_t mask;
+    for (int8_t i = z; i > 0; i--) {
+        mask = 1 << (i - 1);
+        quadKey += '0' + ((x & mask ? 1 : 0) + (y & mask ? 2 : 0));
+    }
+    return quadKey;
+}
+
+static mapbox::geometry::point<double> getMercCoord(int32_t x, int32_t y, int8_t z) {
+    double resolution = (util::M2PI * util::EARTH_RADIUS_M / 256) / std::pow(2.0f, z);
+    return {
+        x * resolution - util::M2PI * util::EARTH_RADIUS_M / 2,
+        y * resolution - util::M2PI * util::EARTH_RADIUS_M / 2,
+    };
+}
+
+static std::string getTileBBox(int32_t x, int32_t y, int8_t z) {
+    // Alter the y for the Google/OSM tile scheme.
+    y = std::pow(2.0f, z) - y - 1;
+
+    auto min = getMercCoord(x * 256, y * 256, z);
+    auto max = getMercCoord((x + 1) * 256, (y + 1) * 256, z);
+
+    return (util::toString(min.x) + "," + util::toString(min.y) + "," +
+            util::toString(max.x) + "," + util::toString(max.y));
+}
+
 Resource Resource::style(const std::string& url) {
     return Resource {
         Resource::Kind::Style,
@@ -64,6 +98,10 @@ Resource Resource::tile(const std::string& urlTemplate,
                 return util::toString(x);
             } else if (token == "y") {
                 return util::toString(y);
+            } else if (token == "quadkey") {
+                return getQuadKey(x, y, z);
+            } else if (token == "bbox-epsg-3857") {
+                return getTileBBox(x, y, z);
             } else if (token == "prefix") {
                 std::string prefix{ 2 };
                 prefix[0] = "0123456789abcdef"[x % 16];
diff --git a/test/storage/resource.cpp b/test/storage/resource.cpp
index 5d6c3bcbf2..02559f3e84 100644
--- a/test/storage/resource.cpp
+++ b/test/storage/resource.cpp
@@ -36,6 +36,62 @@ TEST(Resource, Tile) {
     EXPECT_EQ(1, vectorTile.tileData->x);
     EXPECT_EQ(2, vectorTile.tileData->y);
     EXPECT_EQ(3, vectorTile.tileData->z);
+
+    Resource quadTile = Resource::tile("http://example.com/{quadkey}.png", 2.0, 0, 0, 1);
+    EXPECT_EQ(Resource::Kind::Tile, quadTile.kind);
+    EXPECT_EQ("http://example.com/0.png", quadTile.url);
+    EXPECT_EQ("http://example.com/{quadkey}.png", quadTile.tileData->urlTemplate);
+    EXPECT_EQ(1, quadTile.tileData->pixelRatio);
+    EXPECT_EQ(0, quadTile.tileData->x);
+    EXPECT_EQ(0, quadTile.tileData->y);
+    EXPECT_EQ(1, quadTile.tileData->z);
+
+    quadTile = Resource::tile("http://example.com/{quadkey}.png", 2.0, 0, 0, 2);
+    EXPECT_EQ(Resource::Kind::Tile, quadTile.kind);
+    EXPECT_EQ("http://example.com/00.png", quadTile.url);
+    EXPECT_EQ("http://example.com/{quadkey}.png", quadTile.tileData->urlTemplate);
+    EXPECT_EQ(1, quadTile.tileData->pixelRatio);
+    EXPECT_EQ(0, quadTile.tileData->x);
+    EXPECT_EQ(0, quadTile.tileData->y);
+    EXPECT_EQ(2, quadTile.tileData->z);
+
+    quadTile = Resource::tile("http://example.com/{quadkey}.png", 2.0, 1, 1, 2);
+    EXPECT_EQ(Resource::Kind::Tile, quadTile.kind);
+    EXPECT_EQ("http://example.com/03.png", quadTile.url);
+    EXPECT_EQ("http://example.com/{quadkey}.png", quadTile.tileData->urlTemplate);
+    EXPECT_EQ(1, quadTile.tileData->pixelRatio);
+    EXPECT_EQ(1, quadTile.tileData->x);
+    EXPECT_EQ(1, quadTile.tileData->y);
+    EXPECT_EQ(2, quadTile.tileData->z);
+
+    quadTile = Resource::tile("http://example.com/{quadkey}.png", 2.0, 22914, 52870, 17);
+    EXPECT_EQ(Resource::Kind::Tile, quadTile.kind);
+    EXPECT_EQ("http://example.com/02301322130000230.png", quadTile.url);
+    EXPECT_EQ("http://example.com/{quadkey}.png", quadTile.tileData->urlTemplate);
+    EXPECT_EQ(1, quadTile.tileData->pixelRatio);
+    EXPECT_EQ(22914, quadTile.tileData->x);
+    EXPECT_EQ(52870, quadTile.tileData->y);
+    EXPECT_EQ(17, quadTile.tileData->z);
+    
+    // Test case confirmed by quadkeytools package
+    // https://bitbucket.org/steele/quadkeytools/src/master/test/quadkey.js?fileviewer=file-view-default#quadkey.js-57
+    quadTile = Resource::tile("http://example.com/{quadkey}.png", 2.0, 29, 3, 6);
+    EXPECT_EQ(Resource::Kind::Tile, quadTile.kind);
+    EXPECT_EQ("http://example.com/011123.png", quadTile.url);
+    EXPECT_EQ("http://example.com/{quadkey}.png", quadTile.tileData->urlTemplate);
+    EXPECT_EQ(1, quadTile.tileData->pixelRatio);
+    EXPECT_EQ(29, quadTile.tileData->x);
+    EXPECT_EQ(3, quadTile.tileData->y);
+    EXPECT_EQ(6, quadTile.tileData->z);
+
+    Resource wmsTile = Resource::tile("http://example.com/?bbox={bbox-epsg-3857}", 2.0, 0, 0, 1);
+    EXPECT_EQ(Resource::Kind::Tile, wmsTile.kind);
+    EXPECT_EQ("http://example.com/?bbox=-20037508.342789245,0,0,20037508.342789245", wmsTile.url);
+    EXPECT_EQ("http://example.com/?bbox={bbox-epsg-3857}", wmsTile.tileData->urlTemplate);
+    EXPECT_EQ(1, wmsTile.tileData->pixelRatio);
+    EXPECT_EQ(0, wmsTile.tileData->x);
+    EXPECT_EQ(0, wmsTile.tileData->y);
+    EXPECT_EQ(1, wmsTile.tileData->z);
 }
 
 TEST(Resource, Glyphs) {