[core] refactor URL parsing

3 files changed, 235 insertions, 136 deletions

diff --git a/src/mbgl/util/mapbox.cpp b/src/mbgl/util/mapbox.cpp
index 839924d77c..642945ba07 100644
--- a/src/mbgl/util/mapbox.cpp
+++ b/src/mbgl/util/mapbox.cpp
@@ -1,10 +1,12 @@
 #include <mbgl/util/mapbox.hpp>
 #include <mbgl/util/constants.hpp>
 #include <mbgl/util/logging.hpp>
+#include <mbgl/util/url.hpp>
 
 #include <stdexcept>
 #include <vector>
 #include <iostream>
+#include <cstring>
 
 namespace {
 
@@ -21,188 +23,144 @@ bool isMapboxURL(const std::string& url) {
     return url.compare(0, protocolLength, protocol) == 0;
 }
 
-static std::vector<std::string> getMapboxURLPathname(const std::string& url) {
-    std::vector<std::string> pathname;
-    auto startIndex = protocolLength;
-    auto end = url.find_first_of("?#");
-    if (end == std::string::npos) {
-        end = url.length();
-    }
-    while (startIndex < end) {
-        auto endIndex = url.find("/", startIndex);
-        if (endIndex == std::string::npos) {
-            endIndex = end;
-        }
-        pathname.push_back(url.substr(startIndex, endIndex - startIndex));
-        startIndex = endIndex + 1;
-    }
-    return pathname;
-}
-
-static std::pair<std::string, std::size_t> normalizeQuery(const std::string& url) {
-    std::string query;
-
-    auto queryIdx = url.find("?");
-    if (queryIdx != std::string::npos) {
-        query = url.substr(queryIdx + 1, url.length() - queryIdx + 1);
-        if (!query.empty()) {
-            query = "&" + query;
-        }
-    }
-
-    return std::make_pair(query, queryIdx);
+static bool equals(const std::string& str, const URL::Segment& segment, const char* ref) {
+    return str.compare(segment.first, segment.second, ref) == 0;
 }
 
-std::string normalizeSourceURL(const std::string& baseURL, const std::string& url, const std::string& accessToken) {
-    if (!isMapboxURL(url)) {
-        return url;
+std::string normalizeSourceURL(const std::string& baseURL,
+                               const std::string& str,
+                               const std::string& accessToken) {
+    if (!isMapboxURL(str)) {
+        return str;
     }
-
     if (accessToken.empty()) {
-        throw std::runtime_error("You must provide a Mapbox API access token for Mapbox tile sources");
+        throw std::runtime_error(
+            "You must provide a Mapbox API access token for Mapbox tile sources");
     }
 
-    auto query = normalizeQuery(url);
-    return baseURL + "/v4/" + url.substr(protocolLength, query.second - protocolLength) + ".json?access_token=" + accessToken + "&secure" + query.first;
+    const URL url(str);
+    const auto tpl = baseURL + "/v4/{domain}.json?access_token=" + accessToken + "&secure";
+    return transformURL(tpl, str, url);
 }
 
-std::string normalizeStyleURL(const std::string& baseURL, const std::string& url, const std::string& accessToken) {
-    if (!isMapboxURL(url)) {
-        return url;
+std::string normalizeStyleURL(const std::string& baseURL,
+                              const std::string& str,
+                              const std::string& accessToken) {
+    if (!isMapboxURL(str)) {
+        return str;
     }
 
-    const auto pathname = getMapboxURLPathname(url);
-    if (pathname.size() < 3) {
+    const URL url(str);
+    if (!equals(str, url.domain, "styles")) {
         Log::Error(Event::ParseStyle, "Invalid style URL");
-        return url;
+        return str;
     }
 
-    const auto& user = pathname[1];
-    const auto& id = pathname[2];
-    const bool isDraft = pathname.size() > 3;
-    return baseURL + "/styles/v1/" + user + "/" + id + (isDraft ? "/draft" : "") + "?access_token=" + accessToken + normalizeQuery(url).first;
+    const auto tpl = baseURL + "/styles/v1/{path}?access_token=" + accessToken;
+    return transformURL(tpl, str, url);
 }
 
-std::string normalizeSpriteURL(const std::string& baseURL, const std::string& url, const std::string& accessToken) {
-    if (!isMapboxURL(url)) {
-        return url;
-    }
-
-    const auto pathname = getMapboxURLPathname(url);
-    if (pathname.size() < 3) {
-        Log::Error(Event::ParseStyle, "Invalid sprite URL");
-        return url;
+std::string normalizeSpriteURL(const std::string& baseURL,
+                               const std::string& str,
+                               const std::string& accessToken) {
+    if (!isMapboxURL(str)) {
+        return str;
     }
 
-    const auto& user = pathname[1];
-    const bool isDraft = pathname.size() > 3;
-
-    const auto& name = isDraft ? pathname[3] : pathname[2];
-    const size_t index = name.find_first_of("@.");
-    if (index == std::string::npos) {
+    const URL url(str);
+    if (!equals(str, url.domain, "sprites")) {
         Log::Error(Event::ParseStyle, "Invalid sprite URL");
-        return url;
+        return str;
     }
-    const auto& extension = name.substr(index);
-
-    if (isDraft) {
-        const auto& id = pathname[2];
-        return baseURL + "/styles/v1/" + user + "/" + id + "/draft/sprite" + extension +
-               "?access_token=" + accessToken;
 
-    } else {
-        const auto& id = pathname[2].substr(0, index);
-        return baseURL + "/styles/v1/" + user + "/" + id + "/sprite" + extension + "?access_token=" +
-               accessToken;
-    }
+    const auto tpl =
+        baseURL + "/styles/v1/{directory}{filename}/sprite{extension}?access_token=" + accessToken;
+    return transformURL(tpl, str, url);
 }
 
-std::string normalizeGlyphsURL(const std::string& baseURL, const std::string& url, const std::string& accessToken) {
-    if (!isMapboxURL(url)) {
-        return url;
+std::string normalizeGlyphsURL(const std::string& baseURL,
+                               const std::string& str,
+                               const std::string& accessToken) {
+    if (!isMapboxURL(str)) {
+        return str;
     }
 
-    const auto pathname = getMapboxURLPathname(url);
-    if (pathname.size() < 4) {
-      Log::Error(Event::ParseStyle, "Invalid glyph URL");
-      return url;
+    const URL url(str);
+    if (!equals(str, url.domain, "fonts")) {
+        Log::Error(Event::ParseStyle, "Invalid glyph URL");
+        return str;
     }
 
-    const auto& user = pathname[1];
-    const auto& fontstack = pathname[2];
-    const auto& range = pathname[3];
-
-    return baseURL + "/fonts/v1/" + user + "/" + fontstack + "/" + range + "?access_token=" + accessToken;
+    const auto tpl = baseURL + "/fonts/v1/{path}?access_token=" + accessToken;
+    return transformURL(tpl, str, url);
 }
 
-std::string normalizeTileURL(const std::string& baseURL, const std::string& url, const std::string& accessToken) {
-    if (!isMapboxURL(url)) {
-        return url;
+std::string normalizeTileURL(const std::string& baseURL,
+                             const std::string& str,
+                             const std::string& accessToken) {
+    if (!isMapboxURL(str)) {
+        return str;
     }
 
-    auto query = normalizeQuery(url);
-    return baseURL + "/v4/" + url.substr(sizeof("mapbox://tiles/") - 1, query.second - sizeof("mapbox://tiles/") + 1) + "?access_token=" + accessToken + normalizeQuery(url).first;
-}
-
-std::string canonicalizeTileURL(const std::string& url, SourceType type, uint16_t tileSize) {
-    auto tilesetStartIdx = url.find("/v4/");
-    if (tilesetStartIdx == std::string::npos) {
-        return url;
+    const URL url(str);
+    if (!equals(str, url.domain, "tiles")) {
+        Log::Error(Event::ParseStyle, "Invalid tile URL");
+        return str;
     }
 
-    tilesetStartIdx += sizeof("/v4/") - 1;
+    const auto tpl = baseURL + "/v4/{path}?access_token=" + accessToken;
+    return transformURL(tpl, str, url);
+}
 
-    const auto tilesetEndIdx = url.find("/", tilesetStartIdx);
-    if (tilesetEndIdx == std::string::npos) {
-        return url;
-    }
+std::string
+canonicalizeTileURL(const std::string& str, const SourceType type, const uint16_t tileSize) {
+    const char* version = "v4/";
+    const size_t versionLen = strlen(version);
 
-    auto queryIdx = url.rfind("?");
-    if (queryIdx == std::string::npos) {
-        queryIdx = url.length();
-    }
+    const URL url(str);
+    const Path path(str, url.path.first, url.path.second);
 
-    auto basenameIdx = url.rfind("/", queryIdx);
-    if (basenameIdx == std::string::npos || basenameIdx == queryIdx - 1) {
-        basenameIdx = url.length();
-    } else {
-        basenameIdx += 1;
+    // Make sure that we are dealing with a valid Mapbox tile URL.
+    // Has to be /v4/, with a valid filename + extension
+    if (str.compare(url.path.first, versionLen, version) != 0 || path.filename.second == 0 ||
+        path.extension.second <= 1) {
+        // Not a proper Mapbox tile URL.
+        return str;
     }
 
-    const auto extensionIdx = url.find(".", basenameIdx);
-    if (extensionIdx == std::string::npos || extensionIdx == queryIdx - 1) {
-        return url;
+    // Reassemble the canonical URL from the parts we've parsed before.
+    std::string result = "mapbox://tiles/";
+    result.append(str, path.directory.first + versionLen, path.directory.second - versionLen);
+    result.append(str, path.filename.first, path.filename.second);
+    if (type == SourceType::Raster) {
+        result += tileSize == util::tileSize ? "@2x" : "{ratio}";
     }
 
-    const auto tileset = url.substr(tilesetStartIdx, tilesetEndIdx - tilesetStartIdx);
-    auto extension = url.substr(extensionIdx + 1, queryIdx - extensionIdx - 1);
-
 #if !defined(__ANDROID__) && !defined(__APPLE__) && !defined(QT_IMAGE_DECODERS)
-    // Replace PNG with WebP.
-    if (extension == "png") {
-        extension = "webp";
-    }
+    const bool forceWebP = str.compare(path.extension.first, path.extension.second, ".png") == 0;
+#else
+    const bool forceWebP = false;
 #endif // !defined(__ANDROID__) && !defined(__APPLE__) && !defined(QT_IMAGE_DECODERS)
 
-    std::string result = "mapbox://tiles/" + tileset + "/{z}/{x}/{y}";
-
-    if (type == SourceType::Raster) {
-        result += tileSize == util::tileSize ? "@2x" : "{ratio}";
+    // Replace PNG with WebP if necessary.
+    if (forceWebP) {
+        result += ".webp";
+    } else {
+        result.append(str, path.extension.first, path.extension.second);
     }
 
-    result += "." + extension;
-
-    // get the query and remove access_token, if more parameters exist, add them to the final result
-    if (queryIdx != url.length()) {
-        auto idx = queryIdx;
+    // Append the query string, minus the access token parameter.
+    if (url.query.second > 1) {
+        auto idx = url.query.first;
         bool hasQuery = false;
         while (idx != std::string::npos) {
             idx++; // skip & or ?
-            auto ampersandIdx = url.find("&", idx);
-            if (url.substr(idx, 13) != "access_token=") {
-                result += hasQuery ? "&" : "?";
-                result += url.substr(idx, ampersandIdx != std::string::npos ? ampersandIdx - idx
-                                                                            : std::string::npos);
+            auto ampersandIdx = str.find('&', idx);
+            const char* accessToken = "access_token=";
+            if (str.compare(idx, strlen(accessToken), accessToken) != 0) {
+                result.append(1, hasQuery ? '&' : '?');
+                result.append(str, idx, ampersandIdx != std::string::npos ? ampersandIdx - idx
+                                                                          : std::string::npos);
                 hasQuery = true;
             }
             idx = ampersandIdx;
diff --git a/src/mbgl/util/url.cpp b/src/mbgl/util/url.cpp
index 9831bc9038..f070135213 100644
--- a/src/mbgl/util/url.cpp
+++ b/src/mbgl/util/url.cpp
@@ -1,11 +1,12 @@
 #include <mbgl/util/url.hpp>
+#include <mbgl/util/token.hpp>
 
 #include <iomanip>
 #include <sstream>
 #include <string>
 #include <cstdlib>
 #include <algorithm>
-
+#include <cstring>
 
 namespace {
 
@@ -78,5 +79,104 @@ bool isURL(const std::string& input) {
            (it != input.end() && *it++ == '/');
 }
 
+URL::URL(const std::string& str)
+    : query([&]() -> Segment {
+          const auto hashPos = str.find('#');
+          const auto queryPos = str.find('?');
+          if (queryPos == std::string::npos || hashPos < queryPos) {
+              return { hashPos != std::string::npos ? hashPos : str.size(), 0 };
+          }
+          return { queryPos, (hashPos != std::string::npos ? hashPos : str.size()) - queryPos };
+      }()),
+      scheme([&]() -> Segment {
+          auto schemeEnd = str.find(':');
+          return { 0, schemeEnd == std::string::npos || schemeEnd > query.first ? 0 : schemeEnd };
+      }()),
+      domain([&]() -> Segment {
+          auto domainPos = scheme.first + scheme.second;
+          while (domainPos < query.first && (str[domainPos] == ':' || str[domainPos] == '/')) {
+              ++domainPos;
+          }
+          const bool isData = str.compare(scheme.first, scheme.second, "data") == 0;
+          const auto endPos = str.find(isData ? ',' : '/', domainPos);
+          return { domainPos, std::min(query.first, endPos) - domainPos };
+      }()),
+      path([&]() -> Segment {
+          auto pathPos = domain.first + domain.second;
+          const bool isData = str.compare(scheme.first, scheme.second, "data") == 0;
+          if (isData) {
+              // Skip comma
+              pathPos++;
+          } else {
+              // Skip optional leading slash
+              while (pathPos < query.first && (str[pathPos] == '/')) {
+                  ++pathPos;
+              }
+          }
+          return { pathPos, query.first - pathPos };
+      }()) {
+}
+
+Path::Path(const std::string& str, const size_t pos, const size_t count)
+    : directory([&]() -> Segment {
+          // Finds the string between pos and the first /, if it exists
+          const auto endPos = count == std::string::npos ? str.size() : pos + count;
+          const auto slashPos = str.rfind('/', endPos);
+          return { pos, slashPos == std::string::npos || slashPos < pos ? 0 : slashPos + 1 - pos };
+      }()),
+      extension([&]() -> Segment {
+          auto dotPos = str.rfind('.', pos + count);
+          const auto endPos = count == std::string::npos ? str.size() : pos + count;
+          // Count a preceding @2x to the file extension as well.
+          const char* factor = "@2x";
+          const size_t factorLen = strlen(factor);
+          if (dotPos >= factorLen && dotPos < endPos &&
+              str.compare(dotPos - factorLen, factorLen, factor) == 0) {
+              dotPos -= factorLen;
+          }
+          if (dotPos == std::string::npos || dotPos < directory.first + directory.second) {
+              return { endPos, 0 };
+          }
+          return { dotPos, endPos - dotPos };
+      }()),
+      filename([&]() -> Segment {
+          const auto filePos = directory.first + directory.second;
+          return { filePos, extension.first - filePos };
+      }()) {
+}
+
+std::string transformURL(const std::string& tpl, const std::string& str, const URL& url) {
+    auto result = util::replaceTokens(tpl, [&](const std::string& token) -> std::string {
+        if (token == "path") {
+            return str.substr(url.path.first, url.path.second);
+        } else if (token == "domain") {
+            return str.substr(url.domain.first, url.domain.second);
+        } else if (token == "scheme") {
+            return str.substr(url.scheme.first, url.scheme.second);
+        } else if (token == "directory") {
+            const Path path(str, url.path.first, url.path.second);
+            return str.substr(path.directory.first, path.directory.second);
+        } else if (token == "filename") {
+            const Path path(str, url.path.first, url.path.second);
+            return str.substr(path.filename.first, path.filename.second);
+        } else if (token == "extension") {
+            const Path path(str, url.path.first, url.path.second);
+            return str.substr(path.extension.first, path.extension.second);
+        }
+        return "";
+    });
+
+    // Append the query string if it exists.
+    if (url.query.second > 1) {
+        const auto amp = result.find('?') != std::string::npos ? result.size() : std::string::npos;
+        result.append(str, url.query.first, url.query.second);
+        // Transform the question mark to an ampersand if we had a query string previously.
+        if (amp < result.size()) {
+            result[amp] = '&';
+        }
+    }
+    return result;
+}
+
 } // namespace util
 } // namespace mbgl
diff --git a/src/mbgl/util/url.hpp b/src/mbgl/util/url.hpp
index 2d18f7476a..e361b07a7c 100644
--- a/src/mbgl/util/url.hpp
+++ b/src/mbgl/util/url.hpp
@@ -10,5 +10,46 @@ std::string percentEncode(const std::string&);
 std::string percentDecode(const std::string&);
 bool isURL(const std::string&);
 
+// Class that holds position + lenth pairs for scheme, domain, path + query string of a URL.
+class URL {
+public:
+    using Segment = std::pair<size_t, size_t>; // position, length
+
+    const Segment query;
+    const Segment scheme;
+    const Segment domain;
+    const Segment path;
+
+    URL(const std::string&);
+};
+
+// Class that holds position + lenth pairs for directory, extension, and filename of a path.
+// The extension will contain the preceding ., and optionally a preceding @2x specifier.
+// The filename will not contain the file extension.
+class Path {
+public:
+    using Segment = std::pair<size_t, size_t>; // position, length
+
+    const Segment directory;
+    const Segment extension;
+    const Segment filename;
+
+    Path(const std::string&, size_t pos = 0, size_t count = std::string::npos);
+};
+
+// Parses the given URL and replaces the tokens in template with parts of the URL.
+// When parsing "http://example.com/foo/bar/baz.png", valid tokens are:
+// * {scheme} == "http"
+// * {domain} == "example.com"
+// * {path} == "foo/bar/baz.png"
+// * {directory} == "foo/bar/"
+// * {filename} == "baz"
+// * {extension} == ".png"
+// The query string of the source URL will always be appended.
+std::string transformURL(const std::string& tpl, const std::string& url, const URL&);
+inline std::string transformURL(const std::string& tpl, const std::string& url) {
+    return transformURL(tpl, url, URL(url));
+}
+
 } // namespace util
 } // namespace mbgl