Add dictionary comparing functions and unit tests

base/values.cc

 // Copyright (c) 2010 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 "base/values.h"
 
 #include "base/logging.h"
 #include "base/string_util.h"
 #include "base/utf_string_conversions.h"
 
@@ skipping 856 matching lines @@
               static_cast<const DictionaryValue*>(merge_value));
           continue;
         }
       }
       // All other cases: Make a copy and hook it up.
       SetWithoutPathExpansion(*key, merge_value->DeepCopy());
     }
   }
 }
 
+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) {
 }
 
 ListValue::~ListValue() {
   Clear();
 }
 
 void ListValue::Clear() {
@@ skipping 190 matching lines @@
       return false;
   }
   if (lhs_it != end() || rhs_it != other_list->end())
     return false;
 
   return true;
 }
 
 ValueSerializer::~ValueSerializer() {
 }