Add dictionary comparing functions to DictionaryValue and unit tests

TEST=none
BUG=none

Review URL: http://codereview.chromium.org/3035045

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

1 files changed, 108 insertions, 0 deletions

diff --git a/base/values.cc b/base/values.cc
index 031e1ca..8fdd4ea 100644
--- a/base/values.cc
+++ b/base/values.cc
@@ -874,6 +874,114 @@ void DictionaryValue::MergeDictionary(const DictionaryValue* dictionary) {
   }
 }
 
+bool DictionaryValue::GetDifferingPathsHelper(
+    const std::string& path_prefix,
+    const DictionaryValue* other,
+    std::vector<std::string>* different_paths) const {
+  bool added_path = false;
+  std::map<std::string, Value*>::const_iterator current_this;
+  std::map<std::string, Value*>::const_iterator end_this;
+  current_this = dictionary_.begin();
+  end_this = dictionary_.end();
+  if (!other) {
+    // Recursively add all paths from the |this| dictionary, since they are
+    // not in |other|.
+    for (; current_this != end_this; ++current_this) {
+      std::string full_path_for_key(path_prefix.empty() ? current_this->first :
+                                     path_prefix + "." + current_this->first);
+      different_paths->push_back(full_path_for_key);
+      added_path = true;
+      if (current_this->second->IsType(Value::TYPE_DICTIONARY)) {
+        const DictionaryValue* dictionary_this =
+            static_cast<const DictionaryValue*>(current_this->second);
+        dictionary_this->GetDifferingPathsHelper(full_path_for_key,
+                                                 NULL,
+                                                 different_paths);
+      }
+    }
+  } else {
+    // Both the |this| and |other| dictionaries have entries. Iterate over
+    // both simultaneously. Paths that are in one but not the other are
+    // added to |different_paths| and DictionaryValues are processed
+    // recursively.
+    std::map<std::string, Value*>::const_iterator current_other =
+        other->dictionary_.begin();
+    std::map<std::string, Value*>::const_iterator end_other =
+        other->dictionary_.end();
+    while (current_this != end_this || current_other != end_other) {
+      const Value* recursion_this = NULL;
+      const Value* recursion_other = NULL;
+      const std::string* key_name = NULL;
+      bool current_value_known_equal = false;
+      if (current_this == end_this ||
+          (current_other != end_other &&
+              (current_other->first < current_this->first))) {
+        key_name = &current_other->first;
+        if (current_other->second->IsType(Value::TYPE_DICTIONARY))
+           recursion_this = current_other->second;
+        ++current_other;
+      } else {
+        key_name = &current_this->first;
+        if (current_other == end_other ||
+            current_this->first < current_other->first) {
+          if (current_this->second->IsType(Value::TYPE_DICTIONARY))
+            recursion_this = current_this->second;
+          ++current_this;
+        } else {
+          DCHECK(current_this->first == current_other->first);
+          if (current_this->second->IsType(Value::TYPE_DICTIONARY)) {
+            recursion_this = current_this->second;
+            if (current_other->second->IsType(Value::TYPE_DICTIONARY)) {
+              recursion_other = current_other->second;
+            }
+          } else {
+            if (current_other->second->IsType(Value::TYPE_DICTIONARY)) {
+              recursion_this = current_other->second;
+            } else {
+              current_value_known_equal =
+                 current_this->second->Equals(current_other->second);
+            }
+          }
+          ++current_this;
+          ++current_other;
+        }
+      }
+      const std::string& full_path_for_key(path_prefix.empty() ?
+          *key_name : path_prefix + "." + *key_name);
+      if (!current_value_known_equal)
+        different_paths->push_back(full_path_for_key);
+      if (recursion_this) {
+        const DictionaryValue* dictionary_this =
+            static_cast<const DictionaryValue*>(recursion_this);
+        bool subtree_changed = dictionary_this->GetDifferingPathsHelper(
+            full_path_for_key,
+            static_cast<const DictionaryValue*>(recursion_other),
+            different_paths);
+        if (subtree_changed) {
+          added_path = true;
+        } else {
+          // In order to maintain lexicographical sorting order, directory
+          // paths are pushed "optimistically" assuming that their subtree will
+          // contain differences. If in retrospect there were no differences
+          // in the subtree, the assumption was false and the dictionary path
+          // must be removed.
+          different_paths->pop_back();
+        }
+      } else {
+        added_path |= !current_value_known_equal;
+      }
+    }
+  }
+  return added_path;
+}
+
+void DictionaryValue::GetDifferingPaths(
+    const DictionaryValue* other,
+    std::vector<std::string>* different_paths) const {
+  different_paths->clear();
+  GetDifferingPathsHelper("", other, different_paths);
+}
+
 ///////////////////// ListValue ////////////////////
 
 ListValue::ListValue() : Value(TYPE_LIST) {