Refactor Uses of std::set to std::vector in SimpleFeature

extensions/common/features/simple_feature.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "extensions/common/features/simple_feature.h"
 
+#include <algorithm>
 #include <map>
 #include <vector>
 
 #include "base/bind.h"
 #include "base/command_line.h"
 #include "base/debug/alias.h"
-#include "base/lazy_instance.h"
 #include "base/sha1.h"
 #include "base/stl_util.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/string_util.h"
 #include "base/strings/stringprintf.h"
 #include "extensions/common/extension_api.h"
 #include "extensions/common/features/feature_provider.h"
 #include "extensions/common/switches.h"
 
 namespace extensions {
@@ skipping 12 matching lines @@
 }
 
 Feature::Availability IsAvailableToContextForBind(const Extension* extension,
                                                   Feature::Context context,
                                                   const GURL& url,
                                                   Feature::Platform platform,
                                                   const Feature* feature) {
   return feature->IsAvailableToContext(extension, context, url, platform);
 }
 
-struct Mappings {
-  Mappings() {
-    extension_types["extension"] = Manifest::TYPE_EXTENSION;
-    extension_types["theme"] = Manifest::TYPE_THEME;
-    extension_types["legacy_packaged_app"] = Manifest::TYPE_LEGACY_PACKAGED_APP;
-    extension_types["hosted_app"] = Manifest::TYPE_HOSTED_APP;
-    extension_types["platform_app"] = Manifest::TYPE_PLATFORM_APP;
-    extension_types["shared_module"] = Manifest::TYPE_SHARED_MODULE;
-
-    contexts["blessed_extension"] = Feature::BLESSED_EXTENSION_CONTEXT;
-    contexts["unblessed_extension"] = Feature::UNBLESSED_EXTENSION_CONTEXT;
-    contexts["content_script"] = Feature::CONTENT_SCRIPT_CONTEXT;
-    contexts["web_page"] = Feature::WEB_PAGE_CONTEXT;
-    contexts["blessed_web_page"] = Feature::BLESSED_WEB_PAGE_CONTEXT;
-    contexts["webui"] = Feature::WEBUI_CONTEXT;
-
-    locations["component"] = SimpleFeature::COMPONENT_LOCATION;
-    locations["external_component"] =
-        SimpleFeature::EXTERNAL_COMPONENT_LOCATION;
-    locations["policy"] = SimpleFeature::POLICY_LOCATION;
-
-    platforms["chromeos"] = Feature::CHROMEOS_PLATFORM;
-    platforms["linux"] = Feature::LINUX_PLATFORM;
-    platforms["mac"] = Feature::MACOSX_PLATFORM;
-    platforms["win"] = Feature::WIN_PLATFORM;
-  }
-
-  std::map<std::string, Manifest::Type> extension_types;
-  std::map<std::string, Feature::Context> contexts;
-  std::map<std::string, SimpleFeature::Location> locations;
-  std::map<std::string, Feature::Platform> platforms;
-};
-
-base::LazyInstance<Mappings> g_mappings = LAZY_INSTANCE_INITIALIZER;
-
 // TODO(aa): Can we replace all this manual parsing with JSON schema stuff?
 
-void ParseSet(const base::DictionaryValue* value,
-              const std::string& property,
-              std::set<std::string>* set) {
+void ParseVector(const base::Value* value,
+                 std::vector<std::string>* vector) {
   const base::ListValue* list_value = NULL;
-  if (!value->GetList(property, &list_value))
+  if (!value->GetAsList(&list_value))
     return;
 
-  set->clear();
-  for (size_t i = 0; i < list_value->GetSize(); ++i) {
+  vector->clear();
+  size_t list_size = list_value->GetSize();
+  vector->reserve(list_size);
+  for (size_t i = 0; i < list_size; ++i) {
     std::string str_val;
-    CHECK(list_value->GetString(i, &str_val)) << property << " " << i;
-    set->insert(str_val);
+    CHECK(list_value->GetString(i, &str_val));
+    vector->push_back(str_val);
   }
+  std::sort(vector->begin(), vector->end());
 }
 
 template<typename T>
 void ParseEnum(const std::string& string_value,
                T* enum_value,
                const std::map<std::string, T>& mapping) {
   const auto& iter = mapping.find(string_value);
   if (iter == mapping.end()) {
     // For http://crbug.com/365192.
     char minidump[256];
@@ skipping 11 matching lines @@
                T* enum_value,
                const std::map<std::string, T>& mapping) {
   std::string string_value;
   if (!value->GetString(property, &string_value))
     return;
 
   ParseEnum(string_value, enum_value, mapping);
 }
 
 template<typename T>
-void ParseEnumSet(const base::DictionaryValue* value,
-                  const std::string& property,
-                  std::set<T>* enum_set,
-                  const std::map<std::string, T>& mapping) {
-  if (!value->HasKey(property))
-    return;
-
-  enum_set->clear();
-
+void ParseEnumVector(const base::Value* value,
+                     std::vector<T>* enum_vector,
+                     const std::map<std::string, T>& mapping) {
+  enum_vector->clear();
   std::string property_string;
-  if (value->GetString(property, &property_string)) {
+  if (value->GetAsString(&property_string)) {
     if (property_string == "all") {
+      enum_vector->reserve(mapping.size());
       for (const auto& it : mapping)
-        enum_set->insert(it.second);
+        enum_vector->push_back(it.second);
     }
+    std::sort(enum_vector->begin(), enum_vector->end());
     return;
   }
 
-  std::set<std::string> string_set;
-  ParseSet(value, property, &string_set);
-  for (const auto& str : string_set) {
+  std::vector<std::string> string_vector;
+  ParseVector(value, &string_vector);
+  enum_vector->reserve(string_vector.size());
+  for (const auto& str : string_vector) {
     T enum_value = static_cast<T>(0);
     ParseEnum(str, &enum_value, mapping);
-    enum_set->insert(enum_value);
+    enum_vector->push_back(enum_value);
   }
+  std::sort(enum_vector->begin(), enum_vector->end());
 }
 
 void ParseURLPatterns(const base::DictionaryValue* value,
                       const std::string& key,
                       URLPatternSet* set) {
   const base::ListValue* matches = NULL;
   if (value->GetList(key, &matches)) {
     set->ClearPatterns();
     for (size_t i = 0; i < matches->GetSize(); ++i) {
       std::string pattern;
@@ skipping 89 matching lines @@
   base::CommandLine* command_line = base::CommandLine::ForCurrentProcess();
   if (command_line->HasSwitch(switch_name + "=1"))
     return true;
   if (command_line->HasSwitch(std::string("enable-") + switch_name))
     return true;
   return false;
 }
 
 }  // namespace
 
+struct SimpleFeature::Mappings {
+  Mappings() {
+    extension_types["extension"] = Manifest::TYPE_EXTENSION;
+    extension_types["theme"] = Manifest::TYPE_THEME;
+    extension_types["legacy_packaged_app"] = Manifest::TYPE_LEGACY_PACKAGED_APP;
+    extension_types["hosted_app"] = Manifest::TYPE_HOSTED_APP;
+    extension_types["platform_app"] = Manifest::TYPE_PLATFORM_APP;
+    extension_types["shared_module"] = Manifest::TYPE_SHARED_MODULE;
+
+    contexts["blessed_extension"] = Feature::BLESSED_EXTENSION_CONTEXT;
+    contexts["unblessed_extension"] = Feature::UNBLESSED_EXTENSION_CONTEXT;
+    contexts["content_script"] = Feature::CONTENT_SCRIPT_CONTEXT;
+    contexts["web_page"] = Feature::WEB_PAGE_CONTEXT;
+    contexts["blessed_web_page"] = Feature::BLESSED_WEB_PAGE_CONTEXT;
+    contexts["webui"] = Feature::WEBUI_CONTEXT;
+
+    locations["component"] = SimpleFeature::COMPONENT_LOCATION;
+    locations["external_component"] =
+        SimpleFeature::EXTERNAL_COMPONENT_LOCATION;
+    locations["policy"] = SimpleFeature::POLICY_LOCATION;
+
+    platforms["chromeos"] = Feature::CHROMEOS_PLATFORM;
+    platforms["linux"] = Feature::LINUX_PLATFORM;
+    platforms["mac"] = Feature::MACOSX_PLATFORM;
+    platforms["win"] = Feature::WIN_PLATFORM;
+  }
+
+  std::map<std::string, Manifest::Type> extension_types;
+  std::map<std::string, Feature::Context> contexts;
+  std::map<std::string, SimpleFeature::Location> locations;
+  std::map<std::string, Feature::Platform> platforms;
+};
+
 SimpleFeature::SimpleFeature()
     : location_(UNSPECIFIED_LOCATION),
       min_manifest_version_(0),
       max_manifest_version_(0),
       component_extensions_auto_granted_(true) {}
 
 SimpleFeature::~SimpleFeature() {}
 
 bool SimpleFeature::HasDependencies() const {
   return !dependencies_.empty();
 }
 
 void SimpleFeature::AddFilter(scoped_ptr<SimpleFeatureFilter> filter) {
   filters_.push_back(filter.release());
 }
 
-std::string SimpleFeature::Parse(const base::DictionaryValue* value) {
-  ParseURLPatterns(value, "matches", &matches_);
-  ParseSet(value, "blacklist", &blacklist_);
-  ParseSet(value, "whitelist", &whitelist_);
-  ParseSet(value, "dependencies", &dependencies_);
-  ParseEnumSet<Manifest::Type>(value, "extension_types", &extension_types_,
-                                g_mappings.Get().extension_types);
-  ParseEnumSet<Context>(value, "contexts", &contexts_,
-                        g_mappings.Get().contexts);
-  ParseEnum<Location>(value, "location", &location_,
-                      g_mappings.Get().locations);
-  ParseEnumSet<Platform>(value, "platforms", &platforms_,
-                         g_mappings.Get().platforms);
-  value->GetInteger("min_manifest_version", &min_manifest_version_);
-  value->GetInteger("max_manifest_version", &max_manifest_version_);
+std::string SimpleFeature::Parse(const base::DictionaryValue* dictionary) {
+  static base::LazyInstance<SimpleFeature::Mappings> mappings =
+      LAZY_INSTANCE_INITIALIZER;
 
   no_parent_ = false;
-  value->GetBoolean("noparent", &no_parent_);
-
-  value->GetBoolean("component_extensions_auto_granted",
-                    &component_extensions_auto_granted_);
-
-  value->GetString("command_line_switch", &command_line_switch_);
+  for (base::DictionaryValue::Iterator it(*dictionary);
+      !it.IsAtEnd();
+      it.Advance()) {
+    std::string key = it.key();
+    const base::Value* value = &it.value();
+    if (key == "matches") {
+      ParseURLPatterns(dictionary, "matches", &matches_);
+    } else if (key == "blacklist") {
+      ParseVector(value, &blacklist_);
+    } else if (key == "whitelist") {
+      ParseVector(value, &whitelist_);
+    } else if (key == "dependencies") {
+      ParseVector(value, &dependencies_);
+    } else if (key == "extension_types") {
+      ParseEnumVector<Manifest::Type>(value, &extension_types_,
+                                      mappings.Get().extension_types);
+    } else if (key == "contexts") {
+      ParseEnumVector<Context>(value, &contexts_,
+                               mappings.Get().contexts);
+    } else if (key == "location") {
+      ParseEnum<Location>(dictionary, "location", &location_,
+                          mappings.Get().locations);
+    } else if (key == "platforms") {
+      ParseEnumVector<Platform>(value, &platforms_,
+                                mappings.Get().platforms);
+    } else if (key == "min_manifest_version") {
+      dictionary->GetInteger("min_manifest_version", &min_manifest_version_);
+    } else if (key == "max_manifest_version") {
+      dictionary->GetInteger("max_manifest_version", &max_manifest_version_);
+    } else if (key == "noparent") {
+      dictionary->GetBoolean("noparent", &no_parent_);
+    } else if (key == "component_extensions_auto_granted") {
+      dictionary->GetBoolean("component_extensions_auto_granted",
+                             &component_extensions_auto_granted_);
+    } else if (key == "command_line_switch") {
+      dictionary->GetString("command_line_switch", &command_line_switch_);
+    }
+  }
 
   // NOTE: ideally we'd sanity check that "matches" can be specified if and
   // only if there's a "web_page" or "webui" context, but without
   // (Simple)Features being aware of their own heirarchy this is impossible.
   //
   // For example, we might have feature "foo" available to "web_page" context
   // and "matches" google.com/*. Then a sub-feature "foo.bar" might override
   // "matches" to be chromium.org/*. That sub-feature doesn't need to specify
   // "web_page" context because it's inherited, but we don't know that here.
 
   std::string result;
   for (const auto& filter : filters_) {
-    result = filter->Parse(value);
+    result = filter->Parse(dictionary);
     if (!result.empty())
       break;
   }
 
   return result;
 }
 
 Feature::Availability SimpleFeature::IsAvailableToManifest(
     const std::string& extension_id,
     Manifest::Type type,
     Manifest::Location location,
     int manifest_version,
     Platform platform) const {
   // Check extension type first to avoid granting platform app permissions
   // to component extensions.
   // HACK(kalman): user script -> extension. Solve this in a more generic way
   // when we compile feature files.
   Manifest::Type type_to_check = (type == Manifest::TYPE_USER_SCRIPT) ?
       Manifest::TYPE_EXTENSION : type;
   if (!extension_types_.empty() &&
-      !ContainsKey(extension_types_, type_to_check)) {
+      !ContainsValue(extension_types_, type_to_check)) {
     return CreateAvailability(INVALID_TYPE, type);
   }
 
   if (IsIdInBlacklist(extension_id))
     return CreateAvailability(FOUND_IN_BLACKLIST, type);
 
   // TODO(benwells): don't grant all component extensions.
   // See http://crbug.com/370375 for more details.
   // Component extensions can access any feature.
   // NOTE: Deliberately does not match EXTERNAL_COMPONENT.
@@ skipping 12 matching lines @@
           base::CommandLine::ForCurrentProcess()->GetSwitchValueASCII(
               switches::kWhitelistedExtensionID);
       if (extension_id != whitelist_switch_value)
         return CreateAvailability(NOT_FOUND_IN_WHITELIST, type);
     }
   }
 
   if (!MatchesManifestLocation(location))
     return CreateAvailability(INVALID_LOCATION, type);
 
-  if (!platforms_.empty() && !ContainsKey(platforms_, platform))
+  if (!platforms_.empty() && !ContainsValue(platforms_, platform))
     return CreateAvailability(INVALID_PLATFORM, type);
 
   if (min_manifest_version_ != 0 && manifest_version < min_manifest_version_)
     return CreateAvailability(INVALID_MIN_MANIFEST_VERSION, type);
 
   if (max_manifest_version_ != 0 && manifest_version > max_manifest_version_)
     return CreateAvailability(INVALID_MAX_MANIFEST_VERSION, type);
 
   if (!command_line_switch_.empty() &&
       !IsCommandLineSwitchEnabled(command_line_switch_)) {
@@ skipping 23 matching lines @@
   if (extension) {
     Availability result = IsAvailableToManifest(extension->id(),
                                                 extension->GetType(),
                                                 extension->location(),
                                                 extension->manifest_version(),
                                                 platform);
     if (!result.is_available())
       return result;
   }
 
-  if (!contexts_.empty() && !ContainsKey(contexts_, context))
+  if (!contexts_.empty() && !ContainsValue(contexts_, context))
     return CreateAvailability(INVALID_CONTEXT, context);
 
   // TODO(kalman): Consider checking |matches_| regardless of context type.
   // Fewer surprises, and if the feature configuration wants to isolate
   // "matches" from say "blessed_extension" then they can use complex features.
   if ((context == WEB_PAGE_CONTEXT || context == WEBUI_CONTEXT) &&
       !matches_.MatchesURL(url)) {
     return CreateAvailability(INVALID_URL, url);
   }
 
@@ skipping 111 matching lines @@
 
 bool SimpleFeature::IsIdInBlacklist(const std::string& extension_id) const {
   return IsIdInList(extension_id, blacklist_);
 }
 
 bool SimpleFeature::IsIdInWhitelist(const std::string& extension_id) const {
   return IsIdInList(extension_id, whitelist_);
 }
 
 // static
+bool SimpleFeature::IsIdInArray(const std::string& extension_id,
+                                const char* const array[],
+                                size_t array_length) {
+  if (!IsValidExtensionId(extension_id))
+    return false;
+
+  const char* const* start = array;
+  const char* const* end = array + array_length;
+
+  return ((std::find(start, end, extension_id) != end) ||
+          (std::find(start, end, HashExtensionId(extension_id)) != end));
+}
+
+// static
 bool SimpleFeature::IsIdInList(const std::string& extension_id,
-                               const std::set<std::string>& list) {
-  // Belt-and-suspenders philosophy here. We should be pretty confident by this
-  // point that we've validated the extension ID format, but in case something
-  // slips through, we avoid a class of attack where creative ID manipulation
-  // leads to hash collisions.
-  if (extension_id.length() != 32)  // 128 bits / 4 = 32 mpdecimal characters
+                               const std::vector<std::string>& list) {
+  if (!IsValidExtensionId(extension_id))
     return false;
 
-  return (ContainsKey(list, extension_id) ||
-          ContainsKey(list, HashExtensionId(extension_id)));
+  return (ContainsValue(list, extension_id) ||
+          ContainsValue(list, HashExtensionId(extension_id)));
 }
 
 bool SimpleFeature::MatchesManifestLocation(
     Manifest::Location manifest_location) const {
   switch (location_) {
     case SimpleFeature::UNSPECIFIED_LOCATION:
       return true;
     case SimpleFeature::COMPONENT_LOCATION:
       return manifest_location == Manifest::COMPONENT;
     case SimpleFeature::EXTERNAL_COMPONENT_LOCATION:
@@ skipping 13 matching lines @@
         ExtensionAPI::GetSharedInstance()->GetFeatureDependency(dep_name);
     if (!dependency)
       return CreateAvailability(NOT_PRESENT);
     Availability dependency_availability = checker.Run(dependency);
     if (!dependency_availability.is_available())
       return dependency_availability;
   }
   return CreateAvailability(IS_AVAILABLE);
 }
 
+// static
+bool SimpleFeature::IsValidExtensionId(const std::string& extension_id) {
+  // Belt-and-suspenders philosophy here. We should be pretty confident by this
+  // point that we've validated the extension ID format, but in case something
+  // slips through, we avoid a class of attack where creative ID manipulation
+  // leads to hash collisions.
+  // 128 bits / 4 = 32 mpdecimal characters
+  return (extension_id.length() == 32);
+}
+
 }  // namespace extensions