Allow manifest handlers to declare keys they depend on that must be parsed before them.

chrome/common/extensions/manifest_handler.cc

 // Copyright (c) 2013 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 "chrome/common/extensions/manifest_handler.h"
 
 #include <map>
 
 #include "base/lazy_instance.h"
-#include "base/memory/linked_ptr.h"
+#include "base/stl_util.h"
 #include "chrome/common/extensions/manifest.h"
 
 namespace extensions {
 
 namespace {
 
 class ManifestHandlerRegistry {
  public:
+  ManifestHandlerRegistry() : is_sorted_(false) {
+  }
+
   void RegisterManifestHandler(const std::string& key,
-                               ManifestHandler* handler);
+                               linked_ptr<ManifestHandler> handler);
   bool ParseExtension(Extension* extension, string16* error);
+  void ClearForTesting();
 
  private:
   friend struct base::DefaultLazyInstanceTraits<ManifestHandlerRegistry>;
   typedef std::map<std::string, linked_ptr<ManifestHandler> >
       ManifestHandlerMap;
+  typedef std::map<ManifestHandler*, int> ManifestHandlerPriorityMap;
 
+  // Puts the manifest handlers in order such that each handler comes after
+  // any handlers for their PrerequisiteKeys. If there is no handler for
+  // a prerequisite key, that dependency is simply ignored.
+  // Manifest handlers with circular dependencies are unregistered.
+  void SortManifestHandlers();
+
+  // All registered manifest handlers.
   ManifestHandlerMap handlers_;
+
+  // The priority for each manifest handler. Handlers with lower priority
+  // values are evaluated first.
+  ManifestHandlerPriorityMap priority_map_;
+  bool is_sorted_;
 };
 
 void ManifestHandlerRegistry::RegisterManifestHandler(
-    const std::string& key, ManifestHandler* handler) {
-  handlers_[key] = make_linked_ptr(handler);
+    const std::string& key, linked_ptr<ManifestHandler> handler) {
+  handlers_[key] = handler;
+  is_sorted_ = false;
 }
 
 bool ManifestHandlerRegistry::ParseExtension(Extension* extension,
                                              string16* error) {
-  std::set<ManifestHandler*> handler_set;
+  SortManifestHandlers();
+  std::map<int, ManifestHandler*> handlers_by_priority;
   for (ManifestHandlerMap::iterator iter = handlers_.begin();
        iter != handlers_.end(); ++iter) {
     ManifestHandler* handler = iter->second.get();
     if (extension->manifest()->HasPath(iter->first) ||
-        handler->AlwaysParseForType(extension->GetType()))
-      handler_set.insert(handler);
+        handler->AlwaysParseForType(extension->GetType())) {
+      handlers_by_priority[priority_map_[handler]] = handler;
+    }
   }
-
-  // TODO(yoz): Some handlers may depend on other handlers having already
-  // parsed their keys. Reorder the handlers so that handlers needed earlier
-  // come first in the returned container.
-  for (std::set<ManifestHandler*>::iterator iter = handler_set.begin();
-       iter != handler_set.end(); ++iter) {
-    if (!(*iter)->Parse(extension, error))
+  for (std::map<int, ManifestHandler*>::iterator iter =
+           handlers_by_priority.begin();
+       iter != handlers_by_priority.end(); ++iter) {
+    if (!(iter->second)->Parse(extension, error))
       return false;
   }
   return true;
 }
 
+void ManifestHandlerRegistry::ClearForTesting() {
+  priority_map_.clear();
+  handlers_.clear();
+  is_sorted_ = false;
+}
+
+void ManifestHandlerRegistry::SortManifestHandlers() {
+  if (is_sorted_)
+    return;
+
+  // Forget our existing sort order.
+  priority_map_.clear();
+  std::set<ManifestHandler*> unsorted_handlers;
+  for (ManifestHandlerMap::const_iterator iter = handlers_.begin();
+       iter != handlers_.end(); ++iter) {
+    unsorted_handlers.insert(iter->second.get());
+  }
+
+  int priority = 0;
+  while (true) {
+    std::set<ManifestHandler*> next_unsorted_handlers;
+    for (std::set<ManifestHandler*>::const_iterator iter =
+             unsorted_handlers.begin();

[Matt Perry, 2013/02/01 23:22:37]

I think this would be easier to follow if you made it a recursive helper
function. I'm thinking something like:
- Put every handler into a set of unvisited_handlers.
- Process(string handler_name, set& unvisited_handlers, list& sorted_handlers),
defined as:
  if handler_name not in unvisited_handlers: return
  remove handler_name from unvisited_handlers
  for each dependency of handler_name:
    Process(dependency, unvisited_handler)
  append handler_name to sorted_handlers

Then you just keep calling Process() on the first entry in unvisited_handlers
until it's empty. Once you have sorted_handlers, you don't need a priority map
anymore.

I haven't thought about how to handle circular dependencies this way, but maybe
that could be a separate step.

[Yoyo Zhou, 2013/02/02 00:32:22]

I don't think I find it easier to follow that way.

To handle circular dependencies, you'd also need a third state (unvisited,
visited, sorted), so that if you come to something that's visited but not sorted
yet, you know you've reached your own ancestor.

The reason I didn't make a sorted_handlers list is because you iterate over the
keys in ParseExtension, so you need to get the keys for each handler (so that
you can iterate over the keys in the right order and not call a handler twice).
While you could do this, it's just another auxiliary data structure similar to
priority map, so it doesn't simplify things.

+         iter != unsorted_handlers.end(); ++iter) {
+      ManifestHandler* handler = *iter;
+      const std::vector<std::string>& prerequisites =
+          handler->PrerequisiteKeys();
+      int unsatisfied = prerequisites.size();
+      for (size_t i = 0; i < prerequisites.size(); ++i) {
+        ManifestHandlerMap::const_iterator prereq_iter =
+            handlers_.find(prerequisites[i]);
+        if (prereq_iter == handlers_.end()) {
+          // Nonexistent prerequisite; ignore it.
+          unsatisfied--;
+        } else if (ContainsKey(priority_map_,
+                               prereq_iter->second.get())) {
+          // Prerequisite is in our map.
+          unsatisfied--;
+        }
+      }
+      if (unsatisfied == 0) {
+        priority_map_[handler] = priority;
+        priority++;
+      } else {
+        // Put in the list for next time.
+        next_unsorted_handlers.insert(handler);
+      }
+    }
+    if (next_unsorted_handlers.size() == unsorted_handlers.size())
+      break;
+    unsorted_handlers.swap(next_unsorted_handlers);
+  }
+
+  // If there are any leftover unsorted handlers, they must have had
+  // circular dependencies. Drop them, and log a warning.
+  if (unsorted_handlers.size() > 0) {
+    LOG(WARNING) << "Ignoring extension manifest handlers with "
+                 << "circular dependencies:";
+    for (ManifestHandlerMap::iterator iter = handlers_.begin();
+         iter != handlers_.end();) {
+      ManifestHandlerMap::iterator current = iter++;
+      if (ContainsKey(unsorted_handlers, current->second.get())) {
+        LOG(WARNING) << "key: " << current->first;
+        handlers_.erase(current);
+      }
+    }
+  }
+
+  is_sorted_ = true;
+}
+
 static base::LazyInstance<ManifestHandlerRegistry> g_registry =
     LAZY_INSTANCE_INITIALIZER;
 
+static base::LazyInstance<std::vector<std::string> > g_empty_string_vector =
+    LAZY_INSTANCE_INITIALIZER;
+
 }  // namespace
 
 ManifestHandler::ManifestHandler() {
 }
 
 ManifestHandler::~ManifestHandler() {
 }
 
 bool ManifestHandler::AlwaysParseForType(Manifest::Type type) {
   return false;
 }
 
+const std::vector<std::string>& ManifestHandler::PrerequisiteKeys() {
+  return g_empty_string_vector.Get();
+}
+
 // static
 void ManifestHandler::Register(const std::string& key,
-                               ManifestHandler* handler) {
+                               linked_ptr<ManifestHandler> handler) {
   g_registry.Get().RegisterManifestHandler(key, handler);
 }
 
 // static
 bool ManifestHandler::ParseExtension(Extension* extension, string16* error) {
   return g_registry.Get().ParseExtension(extension, error);
 }
 
+// static
+void ManifestHandler::ClearRegistryForTesting() {
+  g_registry.Get().ClearForTesting();
+}
+
 }  // namespace extensions