ServiceWorker: Support longest-prefix-match for registration scope

content/browser/service_worker/service_worker_storage.cc

Index: content/browser/service_worker/service_worker_storage.cc
diff --git a/content/browser/service_worker/service_worker_storage.cc b/content/browser/service_worker/service_worker_storage.cc
index 62d198bd5aa6e6678b0a66b786222d9d77415c29..6b9d62fab5c3c6fd1e2c61e18f5594a4d15c7ad2 100644
--- a/content/browser/service_worker/service_worker_storage.cc
+++ b/content/browser/service_worker/service_worker_storage.cc
@@ -672,17 +672,20 @@ ServiceWorkerStorage::GetOrCreateRegistration(
 ServiceWorkerRegistration*
 ServiceWorkerStorage::FindInstallingRegistrationForDocument(
     const GURL& document_url) {
-  // TODO(michaeln): if there are multiple matches the one with
-  // the longest scope should win.
+  std::vector<GURL> scopes;

[jsbell, 2014/06/02 18:33:41]

Ugh. This approach is not going to scale well:

* Make a copy of all registered scope URLs
* Linear search over it
* Given the result index, walk over the list again!

We shouldn't rush to optimize, but maybe we can leave some TODOs indicating the
code/storage should be restructured - e.g. pass a Callback into
FindLongestScopeMatch.

(Also, maybe we should partition the maps by origin?)

[nhiroki, 2014/06/03 18:05:03]

Yeah... this is really inefficient way when there is a ton of installing
registrations...
I'm taking a different approach "LongestScopeMatcher" in the latest patchset.
This can resolve 1st and 3rd items on the list. Wdyt?

+  scopes.reserve(installing_registrations_.size());
   for (RegistrationRefsById::const_iterator it =
            installing_registrations_.begin();
        it != installing_registrations_.end(); ++it) {
-    if (ServiceWorkerUtils::ScopeMatches(
-            it->second->pattern(), document_url)) {
-      return it->second;
-    }
+    scopes.push_back(it->second->pattern());
   }
-  return NULL;
+
+  size_t pos = 0;
+  if (!ServiceWorkerUtils::FindLongestScopeMatch(scopes, document_url, &pos))
+    return NULL;
+  RegistrationRefsById::const_iterator it = installing_registrations_.begin();
+  std::advance(it, pos);
+  return it->second;
 }
 
 ServiceWorkerRegistration*
@@ -887,18 +890,18 @@ void ServiceWorkerStorage::FindForDocumentInDB(
   }
 
   // Find one with a pattern match.
-  // TODO(michaeln): if there are multiple matches the one with
-  // the longest scope should win.
   ServiceWorkerDatabase::RegistrationData data;
   ResourceList resources;
   status = ServiceWorkerDatabase::STATUS_ERROR_NOT_FOUND;
-  for (RegistrationList::const_iterator it = registrations.begin();
-       it != registrations.end(); ++it) {
-    if (!ServiceWorkerUtils::ScopeMatches(it->scope, document_url))
-      continue;
-    status = database->ReadRegistration(it->registration_id, origin,
-                                        &data, &resources);
-    break;  // We're done looping.
+
+  std::vector<GURL> scopes;

[jsbell, 2014/06/02 18:33:41]

Another TODO here - we should be able to do this w/o copying everything.

[nhiroki, 2014/06/03 18:05:03]

Ditto. I replaced this with LongestScopeMatcher. It can save the copy cost.

+  scopes.reserve(registrations.size());
+  for (size_t i = 0; i < registrations.size(); ++i)
+    scopes.push_back(registrations[i].scope);
+  size_t pos = 0;
+  if (ServiceWorkerUtils::FindLongestScopeMatch(scopes, document_url, &pos)) {
+    status = database->ReadRegistration(registrations[pos].registration_id,
+                                        origin, &data, &resources);
   }
 
   original_task_runner->PostTask(