Introduce a Factory for Declarative API objects that performs deduping

chrome/browser/extensions/api/declarative/deduping_factory.h

Index: chrome/browser/extensions/api/declarative/deduping_factory.h
diff --git a/chrome/browser/extensions/api/declarative/deduping_factory.h b/chrome/browser/extensions/api/declarative/deduping_factory.h
new file mode 100644
index 0000000000000000000000000000000000000000..57456771e8a104ab001681715e94fd59ded296c2
--- /dev/null
+++ b/chrome/browser/extensions/api/declarative/deduping_factory.h
@@ -0,0 +1,178 @@
+// 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.
+
+#ifndef CHROME_BROWSER_EXTENSIONS_API_DECLARATIVE_DEDUPING_FACTORY_H__
+#define CHROME_BROWSER_EXTENSIONS_API_DECLARATIVE_DEDUPING_FACTORY_H__
+
+#include <list>
+#include <string>
+
+#include "base/compiler_specific.h"
+#include "base/hash_tables.h"
+#include "base/logging.h"
+#include "base/memory/ref_counted.h"
+
+namespace base {
+class DictionaryValue;
+}  // namespace base
+
+namespace extensions {
+
+// Factory class that stores a cache of the last |N| created objects of each
+// kind. These objects need to be immutable, refcounted objects that are derived

[vabr (Chromium), 2013/04/23 12:22:12]

Maybe we should emphasise that this class does not require BaseClassT to be
thread-safe refcounted.

[battre, 2013/04/23 14:20:50]

Done.

+// from BaseClassT. If a new instance of an object is created that is identical
+// to a pre-existing object, it is discarded and the pre-existing object is
+// recycled.
+//
+// BaseClassT needs to provide a comparison operations. Like the following:
+//
+// class BaseClassT {
+//   virtual bool Equals(const BaseClassT* other) const;
+// };
+//
+// The unit test shows an example.
+template<typename BaseClassT>
+class DedupingFactory {
+ public:
+  // Factory methods for BaseClass instances. |dict| contains the json
+  // dictionary that describes the object to be instantiated. |error| is used
+  // to return error messages in case the extension passed an action that was
+  // syntactically correct but semantically incorrect. |bad_message| is set to
+  // true in case |dict| does not confirm to the validated JSON specification.
+  typedef scoped_refptr<const BaseClassT>
+      (* FactoryMethod)(const base::DictionaryValue* /* dict */ ,
+                        std::string* /* error */,
+                        bool* /* bad_message */);
+
+  enum Parameterized {
+    // Two instantiated objects may be different and we need to check for
+    // equality to see whether we can recycle one.
+    IS_PARAMETERIZED,
+    // The objects are not parameterized, i.e. all created instances are the
+    // same and it is sufficient to create a single one.
+    IS_NOT_PARAMETERIZED
+  };
+
+  // Creates a DedupingFactory with a MRU cache of size |max_number_prototypes|
+  // per instance_type. If we find a match within the cache, the factory reuses
+  // that instance instead of creating a new one. The cache size should not be
+  // too large because we probe linearly whether an element is in the cache.
+  explicit DedupingFactory(size_t max_number_prototypes);
+  ~DedupingFactory();
+
+  void RegisterFactoryMethod(const std::string& instance_type,
+                             Parameterized parameterized,
+                             FactoryMethod factory_method);
+
+  scoped_refptr<const BaseClassT> Instantiate(const std::string& instance_type,
+                                              const base::DictionaryValue* dict,
+                                              std::string* error,
+                                              bool* bad_message);
+
+  void ClearPrototypes();
+
+ private:
+  typedef std::string InstanceType;
+  // Cache of previous prototypes in most-recently-used order. Most recently
+  // used objects are at the end.
+  typedef std::list<scoped_refptr<const BaseClassT> > PrototypeList;
+  typedef base::hash_map<InstanceType, PrototypeList> ExistingPrototypes;
+  typedef base::hash_map<InstanceType, FactoryMethod> FactoryMethods;
+  typedef base::hash_set<InstanceType> ParameterizedTypes;
+
+  size_t max_number_prototypes_;

[vabr (Chromium), 2013/04/23 12:22:12]

This should be at least const, but I would even recommend to make it a template
argument. That way it becomes a compile-time constant, will take no space, and
possibly allow more optimizations.

[battre, 2013/04/23 14:20:50]

I have made it const (even though it is pretty uncommon to have const members in
Chrome in my opinion). I had code to make it a template argument but removed it
because the syntax was too cumbersome and I felt that the advantages do not
outweigh the ugly syntax.

[vabr (Chromium), 2013/04/23 15:47:23]

I don't mean to be a pain in the ass, so feel free to ignore this comment. :)

What exactly was cumbersome? It already is a template, so < and > are already
there, there would be one line less in the definition, and the max_number would
be just on another place in the instantiation, no?

Strange syntax is unfortunately the burden of C++, and should not drive the
design decision.
A good reason against template parameters is that they generate too many copies
of the code, trading mostly speed for binary size. If we avoided templates for
syntax, hardly anybody would use them. :)

[battre, 2013/04/29 17:42:34]

The point I disliked was this syntax to access the enums.

DedupingFactory<WebRequestConditionAttribute, 5>::IS_PARAMETERIZED

We can typdef it to hide the parameter.

I suggest to do that in a follow-up CL but frankly I think this is micro
optimization that won't gain anything noticeable.

[vabr (Chromium), 2013/04/30 07:33:31]

Sure, that's fine with me, no follow-up CL necessary.

+  ExistingPrototypes prototypes_;
+  FactoryMethods factory_methods_;
+  ParameterizedTypes parameterized_types_;
+
+  DISALLOW_COPY_AND_ASSIGN(DedupingFactory);
+};
+
+template<typename BaseClassT>
+DedupingFactory<BaseClassT>::DedupingFactory(size_t max_number_prototypes)
+    : max_number_prototypes_(max_number_prototypes) {}
+
+template<typename BaseClassT>
+DedupingFactory<BaseClassT>::~DedupingFactory() {}
+
+template<typename BaseClassT>
+void DedupingFactory<BaseClassT>::RegisterFactoryMethod(
+    const std::string& instance_type,
+    DedupingFactory<BaseClassT>::Parameterized parameterized,
+    FactoryMethod factory_method) {
+  DCHECK(factory_methods_.find(instance_type) == factory_methods_.end());

[vabr (Chromium), 2013/04/23 12:22:12]

nit: !ContainsKey(factory_methods_, instance_type)

[battre, 2013/04/23 14:20:50]

Done.

+  factory_methods_[instance_type] = factory_method;
+  if (parameterized == IS_PARAMETERIZED)
+    parameterized_types_.insert(instance_type);
+}
+
+template<typename BaseClassT>
+scoped_refptr<const BaseClassT> DedupingFactory<BaseClassT>::Instantiate(
+    const std::string& instance_type,
+    const base::DictionaryValue* dict,
+    std::string* error,
+    bool* bad_message) {
+  typename FactoryMethods::const_iterator factory_method_iter =
+      factory_methods_.find(instance_type);
+  if (factory_method_iter == factory_methods_.end()) {
+    *error = "Invalid instance type " + instance_type;
+    *bad_message = true;
+    return scoped_refptr<const BaseClassT>();
+  }
+
+  FactoryMethod factory_method = factory_method_iter->second;
+
+  PrototypeList& prototypes = prototypes_[instance_type];
+
+  // We can take a shortcut for objects that are not parameterized. For those
+  // only a single instance may ever exist so we can simplify the creation
+  // logic.
+  if (parameterized_types_.find(instance_type) == parameterized_types_.end()) {

[vabr (Chromium), 2013/04/23 12:22:12]

nit: !ContainsKey(parametrized_types_, instance_type)

[battre, 2013/04/23 14:20:50]

Done.

+    if (prototypes.empty()) {
+      scoped_refptr<const BaseClassT> new_object =
+          (*factory_method)(dict, error, bad_message);
+      if (!new_object || !error->empty() || *bad_message)
+        return scoped_refptr<const BaseClassT>();
+      prototypes.push_back(new_object);
+    }
+    return prototypes.front();
+  }
+
+  // Handle parameterized objects.
+  scoped_refptr<const BaseClassT> new_object =
+      (*factory_method)(dict, error, bad_message);
+  if (!new_object || !error->empty() || *bad_message)
+    return scoped_refptr<const BaseClassT>();
+
+  size_t length = 0;
+  for (typename PrototypeList::iterator i = prototypes.begin();
+       i != prototypes.end();
+       ++i) {
+    if ((*i)->Equals(new_object.get())) {
+      // Move the old object to the end of the queue so that it gets
+      // discarded later.
+      scoped_refptr<const BaseClassT> old_object = *i;
+      prototypes.erase(i);
+      prototypes.push_back(old_object);
+      return old_object;
+    }
+    ++length;
+  }
+  prototypes.push_back(new_object);
+  ++length;
+
+  if (length > max_number_prototypes_)
+    prototypes.pop_front();

[vabr (Chromium), 2013/04/23 12:22:12]

If this goes just before the push_back (adjusting "length >
max_number_prototypes_" to "length >= max_number_prototypes_"), we keep the
prototypes' length bounded by max_number_prototypes_ all times.

[battre, 2013/04/23 14:20:50]

Done.

+
+  return new_object;
+}
+
+template<typename BaseClassT>
+void DedupingFactory<BaseClassT>::ClearPrototypes() {
+  prototypes_.clear();
+}
+
+}  // namespace extensions
+
+#endif  // CHROME_BROWSER_EXTENSIONS_API_DECLARATIVE_DEDUPING_FACTORY_H__