Optimize ExtensionAPI::IsAnyFeatureAvailableToContext from O(#features) to O(#children + log #features).

This also replaces O(N) string allocations with 1 and moves the top-level
feature check to the top of the function to provide a quick exit when the
context has full access.

And it adds an IsAvailable() overload taking a Feature to avoid the string
copies in GetFeatureDependency().

BUG=305000

Review URL: https://codereview.chromium.org/107473004

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@241706 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 40 insertions, 20 deletions

diff --git a/extensions/common/extension_api.cc b/extensions/common/extension_api.cc
index 13c1ce3..710dc51 100644
--- a/extensions/common/extension_api.cc
+++ b/extensions/common/extension_api.cc
@@ -282,21 +282,19 @@ bool ExtensionAPI::IsAnyFeatureAvailableToContext(const Feature& api,
                                                   const GURL& url) {
   FeatureProviderMap::iterator provider = dependency_providers_.find("api");
   CHECK(provider != dependency_providers_.end());
-  const std::vector<std::string>& features =
-      provider->second->GetAllFeatureNames();
+  if (IsAvailable(api, extension, context, url).is_available())
+    return true;
 
   // Check to see if there are any parts of this API that are allowed in this
   // context.
-  for (std::vector<std::string>::const_iterator i = features.begin();
-       i != features.end(); ++i) {
-    const std::string& feature_name = *i;
-    if (feature_name != api.name() &&
-        feature_name.find(api.name() + ".") == 0) {
-      if (IsAvailable(feature_name, extension, context, url).is_available())
-        return true;
-    }
+  const std::vector<Feature*> features = provider->second->GetChildren(api);
+  for (std::vector<Feature*>::const_iterator feature = features.begin();
+       feature != features.end();
+       ++feature) {
+    if (IsAvailable(**feature, extension, context, url).is_available())
+      return true;
   }
-  return IsAvailable(api.name(), extension, context, url).is_available();
+  return false;
 }
 
 Feature::Availability ExtensionAPI::IsAvailable(const std::string& full_name,
@@ -305,14 +303,20 @@ Feature::Availability ExtensionAPI::IsAvailable(const std::string& full_name,
                                                 const GURL& url) {
   Feature* feature = GetFeatureDependency(full_name);
   CHECK(feature) << full_name;
+  return IsAvailable(*feature, extension, context, url);
+}
 
+Feature::Availability ExtensionAPI::IsAvailable(const Feature& feature,
+                                                const Extension* extension,
+                                                Feature::Context context,
+                                                const GURL& url) {
   Feature::Availability availability =
-      feature->IsAvailableToContext(extension, context, url);
+      feature.IsAvailableToContext(extension, context, url);
   if (!availability.is_available())
     return availability;
 
-  for (std::set<std::string>::iterator iter = feature->dependencies().begin();
-       iter != feature->dependencies().end(); ++iter) {
+  for (std::set<std::string>::iterator iter = feature.dependencies().begin();
+       iter != feature.dependencies().end(); ++iter) {
     Feature::Availability dependency_availability =
         IsAvailable(*iter, extension, context, url);
     if (!dependency_availability.is_available())
diff --git a/extensions/common/extension_api.h b/extensions/common/extension_api.h
index a6b0982..024f594 100644
--- a/extensions/common/extension_api.h
+++ b/extensions/common/extension_api.h
@@ -65,10 +65,15 @@ class ExtensionAPI {
   void RegisterDependencyProvider(const std::string& name,
                                   FeatureProvider* provider);
 
-  // Returns true if the specified API is available. |api_full_name| can be
-  // either a namespace name (like "bookmarks") or a member name (like
-  // "bookmarks.create"). Returns true if the feature and all of its
-  // dependencies are available to the specified context.
+  // Returns true if the specified API is available. Returns true if the feature
+  // and all of its dependencies are available to the specified context.
+  Feature::Availability IsAvailable(const Feature& api,
+                                    const Extension* extension,
+                                    Feature::Context context,
+                                    const GURL& url);
+  // Same as the previous overload, but takes a feature name instead of an
+  // object. |api_full_name| can be either a namespace name (like "bookmarks")
+  // or a member name (like "bookmarks.create").
   Feature::Availability IsAvailable(const std::string& api_full_name,
                                     const Extension* extension,
                                     Feature::Context context,
diff --git a/extensions/common/extension_api_stub.cc b/extensions/common/extension_api_stub.cc
index 1df5fc0..0a2468a 100644
--- a/extensions/common/extension_api_stub.cc
+++ b/extensions/common/extension_api_stub.cc
@@ -29,6 +29,14 @@ Feature::Availability ExtensionAPI::IsAvailable(
   return Feature::CreateAvailability(Feature::NOT_PRESENT, "");
 }
 
+Feature::Availability ExtensionAPI::IsAvailable(
+    const Feature& api,
+    const Extension* extension,
+    Feature::Context context,
+    const GURL& url) {
+  return Feature::CreateAvailability(Feature::NOT_PRESENT, "");
+}
+
 bool ExtensionAPI::IsAnyFeatureAvailableToContext(const Feature& api,
                                                   const Extension* extension,
                                                   Feature::Context context,
diff --git a/extensions/common/features/feature.h b/extensions/common/features/feature.h
index 0caebf6..5d2d8f3 100644
--- a/extensions/common/features/feature.h
+++ b/extensions/common/features/feature.h
@@ -101,7 +101,7 @@ class Feature {
 
   const std::string& name() const { return name_; }
   void set_name(const std::string& name) { name_ = name; }
-  const std::set<std::string>& dependencies() { return dependencies_; }
+  const std::set<std::string>& dependencies() const { return dependencies_; }
   bool no_parent() const { return no_parent_; }
 
   // Gets the platform the code is currently running on.
diff --git a/extensions/common/features/feature_provider.h b/extensions/common/features/feature_provider.h
index 0951196..97f94c65 100644
--- a/extensions/common/features/feature_provider.h
+++ b/extensions/common/features/feature_provider.h
@@ -24,7 +24,10 @@ class FeatureProvider {
   // Returns the parent feature of |feature|, or NULL if there isn't one.
   virtual Feature* GetParent(Feature* feature) const = 0;
 
-  // Returns all features described by this instance.
+  // Returns the features inside the |parent| namespace, recursively.
+  virtual std::vector<Feature*> GetChildren(const Feature& parent) const = 0;
+
+  // Returns all features described by this instance, in asciibetical order.
   virtual const std::vector<std::string>& GetAllFeatureNames() const = 0;
 
   // Gets a feature provider for a specific feature type, like "permission".