Add a way to checksum bookmark data to help determine if the

bookmarks file was changed by the user between two chrome runs.
- BookmarkCodec now serializes a checksum of bookmark data along
  side bookmark data during encoding.
- During decoding BookmarkCodec computes the checksum of deserialized
  data, and it also reads the checksum in the file.
- BookmarkCodec exposes both the checksums via getters.
- Add unit tests for BookmarkCodec, right now only checksum related.

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

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

3 files changed, 290 insertions, 23 deletions

diff --git a/chrome/browser/bookmarks/bookmark_codec.cc b/chrome/browser/bookmarks/bookmark_codec.cc
index 8d61d37..5c2f186 100644
--- a/chrome/browser/bookmarks/bookmark_codec.cc
+++ b/chrome/browser/bookmarks/bookmark_codec.cc
@@ -17,6 +17,7 @@ const wchar_t* BookmarkCodec::kRootsKey = L"roots";
 const wchar_t* BookmarkCodec::kRootFolderNameKey = L"bookmark_bar";
 const wchar_t* BookmarkCodec::kOtherBookmarFolderNameKey = L"other";
 const wchar_t* BookmarkCodec::kVersionKey = L"version";
+const wchar_t* BookmarkCodec::kChecksumKey = L"checksum";
 const wchar_t* BookmarkCodec::kTypeKey = L"type";
 const wchar_t* BookmarkCodec::kNameKey = L"name";
 const wchar_t* BookmarkCodec::kDateAddedKey = L"date_added";
@@ -35,17 +36,57 @@ Value* BookmarkCodec::Encode(BookmarkModel* model) {
 
 Value* BookmarkCodec::Encode(BookmarkNode* bookmark_bar_node,
                              BookmarkNode* other_folder_node) {
+  InitializeChecksum();
   DictionaryValue* roots = new DictionaryValue();
   roots->Set(kRootFolderNameKey, EncodeNode(bookmark_bar_node));
   roots->Set(kOtherBookmarFolderNameKey, EncodeNode(other_folder_node));
 
   DictionaryValue* main = new DictionaryValue();
   main->SetInteger(kVersionKey, kCurrentVersion);
+  FinalizeChecksum();
+  // We are going to store the computed checksum. So set stored checksum to be
+  // the same as computed checksum.
+  stored_checksum_ = computed_checksum_;
+  main->Set(kChecksumKey, Value::CreateStringValue(computed_checksum_));
   main->Set(kRootsKey, roots);
   return main;
 }
 
 bool BookmarkCodec::Decode(BookmarkModel* model, const Value& value) {
+  stored_checksum_.clear();
+  InitializeChecksum();
+  bool success = DecodeHelper(model, value);
+  FinalizeChecksum();
+  return success;
+}
+
+Value* BookmarkCodec::EncodeNode(BookmarkNode* node) {
+  DictionaryValue* value = new DictionaryValue();
+  const std::wstring& title = node->GetTitle();
+  value->SetString(kNameKey, title);
+  value->SetString(kDateAddedKey,
+                   Int64ToWString(node->date_added().ToInternalValue()));
+  if (node->GetType() == history::StarredEntry::URL) {
+    value->SetString(kTypeKey, kTypeURL);
+    std::wstring url = UTF8ToWide(node->GetURL().possibly_invalid_spec());
+    value->SetString(kURLKey, url);
+    UpdateChecksumWithUrlNode(title, url);
+  } else {
+    value->SetString(kTypeKey, kTypeFolder);
+    value->SetString(kDateModifiedKey,
+                     Int64ToWString(node->date_group_modified().
+                                    ToInternalValue()));
+    UpdateChecksumWithFolderNode(title);
+
+    ListValue* child_values = new ListValue();
+    value->Set(kChildrenKey, child_values);
+    for (int i = 0; i < node->GetChildCount(); ++i)
+      child_values->Append(EncodeNode(node->GetChild(i)));
+  }
+  return value;
+}
+
+bool BookmarkCodec::DecodeHelper(BookmarkModel* model, const Value& value) {
   if (value.GetType() != Value::TYPE_DICTIONARY)
     return false;  // Unexpected type.
 
@@ -55,6 +96,16 @@ bool BookmarkCodec::Decode(BookmarkModel* model, const Value& value) {
   if (!d_value.GetInteger(kVersionKey, &version) || version != kCurrentVersion)
     return false;  // Unknown version.
 
+  Value* checksum_value;
+  if (d_value.Get(kChecksumKey, &checksum_value)) {
+    if (checksum_value->GetType() != Value::TYPE_STRING)
+      return false;
+    StringValue* checksum_value_str = static_cast<StringValue*>(checksum_value);
+    if (!checksum_value_str->GetAsString(&stored_checksum_))
+      return false;
+  }
+
+
   Value* roots;
   if (!d_value.Get(kRootsKey, &roots))
     return false;  // No roots.
@@ -84,30 +135,8 @@ bool BookmarkCodec::Decode(BookmarkModel* model, const Value& value) {
       l10n_util::GetString(IDS_BOOMARK_BAR_FOLDER_NAME));
   model->other_node()->SetTitle(
       l10n_util::GetString(IDS_BOOMARK_BAR_OTHER_FOLDER_NAME));
-  return true;
-}
 
-Value* BookmarkCodec::EncodeNode(BookmarkNode* node) {
-  DictionaryValue* value = new DictionaryValue();
-  value->SetString(kNameKey, node->GetTitle());
-  value->SetString(kDateAddedKey,
-                   Int64ToWString(node->date_added().ToInternalValue()));
-  if (node->GetType() == history::StarredEntry::URL) {
-    value->SetString(kTypeKey, kTypeURL);
-    value->SetString(kURLKey,
-                     UTF8ToWide(node->GetURL().possibly_invalid_spec()));
-  } else {
-    value->SetString(kTypeKey, kTypeFolder);
-    value->SetString(kDateModifiedKey,
-                     Int64ToWString(node->date_group_modified().
-                                    ToInternalValue()));
-
-    ListValue* child_values = new ListValue();
-    value->Set(kChildrenKey, child_values);
-    for (int i = 0; i < node->GetChildCount(); ++i)
-      child_values->Append(EncodeNode(node->GetChild(i)));
-  }
-  return value;
+  return true;
 }
 
 bool BookmarkCodec::DecodeChildren(BookmarkModel* model,
@@ -160,6 +189,7 @@ bool BookmarkCodec::DecodeNode(BookmarkModel* model,
     if (parent)
       parent->Add(parent->GetChildCount(), node);
     node->type_ = history::StarredEntry::URL;
+    UpdateChecksumWithUrlNode(title, url_string);
   } else {
     std::wstring last_modified_date;
     if (!value.GetString(kDateModifiedKey, &last_modified_date))
@@ -181,6 +211,7 @@ bool BookmarkCodec::DecodeNode(BookmarkModel* model,
     if (parent)
       parent->Add(parent->GetChildCount(), node);
 
+    UpdateChecksumWithFolderNode(title);
     if (!DecodeChildren(model, *static_cast<ListValue*>(child_values), node))
       return false;
   }
@@ -190,3 +221,34 @@ bool BookmarkCodec::DecodeNode(BookmarkModel* model,
       StringToInt64(WideToUTF16Hack(date_added_string)));
   return true;
 }
+
+void BookmarkCodec::UpdateChecksum(const std::string& str) {
+  MD5Update(&md5_context_, str.data(), str.length() * sizeof(char));
+}
+
+void BookmarkCodec::UpdateChecksum(const std::wstring& str) {
+  MD5Update(&md5_context_, str.data(), str.length() * sizeof(wchar_t));
+}
+
+void BookmarkCodec::UpdateChecksumWithUrlNode(const std::wstring& title,
+                                              const std::wstring& url) {
+  UpdateChecksum(title);
+  UpdateChecksum(kTypeURL);
+  UpdateChecksum(url);
+}
+
+void BookmarkCodec::UpdateChecksumWithFolderNode(const std::wstring& title) {
+  UpdateChecksum(title);
+  UpdateChecksum(kTypeFolder);
+}
+
+void BookmarkCodec::InitializeChecksum() {
+  MD5Init(&md5_context_);
+}
+
+void BookmarkCodec::FinalizeChecksum() {
+  MD5Digest digest;
+  MD5Final(&digest, &md5_context_);
+  computed_checksum_ = MD5DigestToBase16(digest);
+}
+
diff --git a/chrome/browser/bookmarks/bookmark_codec.h b/chrome/browser/bookmarks/bookmark_codec.h
index 4e1fb81..fb9d06f 100644
--- a/chrome/browser/bookmarks/bookmark_codec.h
+++ b/chrome/browser/bookmarks/bookmark_codec.h
@@ -9,7 +9,10 @@
 #ifndef CHROME_BROWSER_BOOKMARKS_BOOKMARK_CODEC_H_
 #define CHROME_BROWSER_BOOKMARKS_BOOKMARK_CODEC_H_
 
+#include <string>
+
 #include "base/basictypes.h"
+#include "base/md5.h"
 
 class BookmarkModel;
 class BookmarkNode;
@@ -43,11 +46,22 @@ class BookmarkCodec {
   // nodes.
   bool Decode(BookmarkModel* model, const Value& value);
 
+  // Returns the checksum computed during last encoding/decoding call.
+  const std::string& computed_checksum() const { return computed_checksum_; }
+
+  // Returns the checksum that's stored in the file. After a call to Encode,
+  // the computed and stored checksums are the same since the computed checksum
+  // is stored to the file. After a call to decode, the computed checksum can
+  // differ from the stored checksum if the file contents were changed by the
+  // user.
+  const std::string& stored_checksum() const { return stored_checksum_; }
+
   // Names of the various keys written to the Value.
   static const wchar_t* kRootsKey;
   static const wchar_t* kRootFolderNameKey;
   static const wchar_t* kOtherBookmarFolderNameKey;
   static const wchar_t* kVersionKey;
+  static const wchar_t* kChecksumKey;
   static const wchar_t* kTypeKey;
   static const wchar_t* kNameKey;
   static const wchar_t* kDateAddedKey;
@@ -64,6 +78,9 @@ class BookmarkCodec {
   // The caller takes ownership of the returned object.
   Value* EncodeNode(BookmarkNode* node);
 
+  // Helper to perform decoding.
+  bool DecodeHelper(BookmarkModel* model, const Value& value);
+
   // Decodes the children of the specified node. Returns true on success.
   bool DecodeChildren(BookmarkModel* model,
                       const ListValue& child_value_list,
@@ -77,6 +94,31 @@ class BookmarkCodec {
                   BookmarkNode* parent,
                   BookmarkNode* node);
 
+  // Updates the check-sum with the given string.
+  void UpdateChecksum(const std::string& str);
+  void UpdateChecksum(const std::wstring& str);
+
+  // Updates the check-sum with the given contents of URL/folder bookmark node.
+  // NOTE: These functions take in individual properties of a bookmark node
+  // instead of taking in a BookmarkNode for efficiency so that we don't convert
+  // varous data-types to wide strings multiple times - once for serializing
+  // and once for computing the check-sum.
+  void UpdateChecksumWithUrlNode(const std::wstring& title,
+                                 const std::wstring& url);
+  void UpdateChecksumWithFolderNode(const std::wstring& title);
+
+  // Initializes/Finalizes the checksum.
+  void InitializeChecksum();
+  void FinalizeChecksum();
+
+  // MD5 context used to compute MD5 hash of all bookmark data.
+  MD5Context md5_context_;
+
+  // Checksums.
+  std::string computed_checksum_;
+  std::string stored_checksum_;
+
+
   DISALLOW_COPY_AND_ASSIGN(BookmarkCodec);
 };
 
diff --git a/chrome/browser/bookmarks/bookmark_codec_unittest.cc b/chrome/browser/bookmarks/bookmark_codec_unittest.cc
new file mode 100644
index 0000000..59e0af5
--- /dev/null
+++ b/chrome/browser/bookmarks/bookmark_codec_unittest.cc
@@ -0,0 +1,163 @@
+// Copyright (c) 2006-2009 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/scoped_ptr.h"
+#include "base/string_util.h"
+#include "base/values.h"
+#include "chrome/browser/bookmarks/bookmark_model.h"
+#include "chrome/browser/bookmarks/bookmark_codec.h"
+#include "chrome/browser/bookmarks/bookmark_utils.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+class BookmarkCodecTest : public testing::Test {
+ protected:
+  // Helpers to create bookmark models with different data.
+  // Callers own the returned instances.
+  BookmarkModel* CreateModelWithOneUrl() {
+    scoped_ptr<BookmarkModel> model(new BookmarkModel(NULL));
+    BookmarkNode* bookmark_bar = model->GetBookmarkBarNode();
+    model->AddURL(bookmark_bar, 0, L"foo", GURL(L"http://www.foo.com"));
+    return model.release();
+  }
+  BookmarkModel* CreateModelWithTwoUrls() {
+    scoped_ptr<BookmarkModel> model(new BookmarkModel(NULL));
+    BookmarkNode* bookmark_bar = model->GetBookmarkBarNode();
+    model->AddURL(bookmark_bar, 0, L"foo", GURL(L"http://www.foo.com"));
+    model->AddURL(bookmark_bar, 1, L"bar", GURL(L"http://www.bar.com"));
+    return model.release();
+  }
+
+  void GetBookmarksBarChildValue(Value* value,
+                                 size_t index,
+                                 DictionaryValue** result_value) {
+    ASSERT_EQ(Value::TYPE_DICTIONARY, value->GetType());
+
+    DictionaryValue* d_value = static_cast<DictionaryValue*>(value);
+    Value* roots;
+    ASSERT_TRUE(d_value->Get(BookmarkCodec::kRootsKey, &roots));
+    ASSERT_EQ(Value::TYPE_DICTIONARY, roots->GetType());
+
+    DictionaryValue* roots_d_value = static_cast<DictionaryValue*>(roots);
+    Value* bb_value;
+    ASSERT_TRUE(roots_d_value->Get(BookmarkCodec::kRootFolderNameKey,
+                                   &bb_value));
+    ASSERT_EQ(Value::TYPE_DICTIONARY, bb_value->GetType());
+
+    DictionaryValue* bb_d_value = static_cast<DictionaryValue*>(bb_value);
+    Value* bb_children_value;
+    ASSERT_TRUE(bb_d_value->Get(BookmarkCodec::kChildrenKey,
+                                &bb_children_value));
+    ASSERT_EQ(Value::TYPE_LIST, bb_children_value->GetType());
+
+    ListValue* bb_children_l_value = static_cast<ListValue*>(bb_children_value);
+    Value* child_value;
+    ASSERT_TRUE(bb_children_l_value->Get(index, &child_value));
+    ASSERT_EQ(Value::TYPE_DICTIONARY, child_value->GetType());
+
+    *result_value = static_cast<DictionaryValue*>(child_value);
+  }
+
+  Value* EncodeHelper(BookmarkModel* model, std::string* checksum) {
+    BookmarkCodec encoder;
+    // Computed and stored checksums should be empty.
+    EXPECT_EQ("", encoder.computed_checksum());
+    EXPECT_EQ("", encoder.stored_checksum());
+
+    scoped_ptr<Value> value(encoder.Encode(model));
+    const std::string& computed_checksum = encoder.computed_checksum();
+    const std::string& stored_checksum = encoder.stored_checksum();
+ 
+    // Computed and stored checksums should not be empty and should be equal.
+    EXPECT_FALSE(computed_checksum.empty());
+    EXPECT_FALSE(stored_checksum.empty());
+    EXPECT_EQ(computed_checksum, stored_checksum);
+
+    *checksum = computed_checksum;
+    return value.release();
+  }
+
+  BookmarkModel* DecodeHelper(const Value& value,
+                              const std::string& expected_stored_checksum,
+                              std::string* computed_checksum,
+                              bool expected_changes) {
+    BookmarkCodec decoder;
+    // Computed and stored checksums should be empty.
+    EXPECT_EQ("", decoder.computed_checksum());
+    EXPECT_EQ("", decoder.stored_checksum());
+
+    scoped_ptr<BookmarkModel> model(new BookmarkModel(NULL));
+    EXPECT_TRUE(decoder.Decode(model.get(), value));
+
+    *computed_checksum = decoder.computed_checksum();
+    const std::string& stored_checksum = decoder.stored_checksum();
+ 
+    // Computed and stored checksums should not be empty.
+    EXPECT_FALSE(computed_checksum->empty());
+    EXPECT_FALSE(stored_checksum.empty());
+
+    // Stored checksum should be as expected.
+    EXPECT_EQ(expected_stored_checksum, stored_checksum);
+
+    // The two checksums should be equal if expected_changes is true; otherwise
+    // they should be different.
+    if (expected_changes)
+      EXPECT_NE(*computed_checksum, stored_checksum);
+    else
+      EXPECT_EQ(*computed_checksum, stored_checksum);
+
+    return model.release();
+  }
+};
+
+TEST_F(BookmarkCodecTest, ChecksumEncodeDecodeTest) {
+  scoped_ptr<BookmarkModel> model_to_encode(CreateModelWithOneUrl());
+  std::string enc_checksum;
+  scoped_ptr<Value> value(EncodeHelper(model_to_encode.get(), &enc_checksum));
+
+  EXPECT_TRUE(value.get() != NULL);
+
+  std::string dec_checksum;
+  scoped_ptr<BookmarkModel> decoded_model(DecodeHelper(
+      *value.get(), enc_checksum, &dec_checksum, false));
+}
+
+TEST_F(BookmarkCodecTest, ChecksumEncodeIdenticalModelsTest) {
+  // Encode two identical models and make sure the check-sums are same as long
+  // as the data is the same.
+  scoped_ptr<BookmarkModel> model1(CreateModelWithOneUrl());
+  std::string enc_checksum1;
+  scoped_ptr<Value> value1(EncodeHelper(model1.get(), &enc_checksum1));
+  EXPECT_TRUE(value1.get() != NULL);
+
+  scoped_ptr<BookmarkModel> model2(CreateModelWithOneUrl());
+  std::string enc_checksum2;
+  scoped_ptr<Value> value2(EncodeHelper(model2.get(), &enc_checksum2));
+  EXPECT_TRUE(value2.get() != NULL);
+
+  ASSERT_EQ(enc_checksum1, enc_checksum2);
+}
+
+TEST_F(BookmarkCodecTest, ChecksumManualEditTest) {
+  scoped_ptr<BookmarkModel> model_to_encode(CreateModelWithOneUrl());
+  std::string enc_checksum;
+  scoped_ptr<Value> value(EncodeHelper(model_to_encode.get(), &enc_checksum));
+
+  EXPECT_TRUE(value.get() != NULL);
+
+  // Change something in the encoded value before decoding it.
+  DictionaryValue* child1_value;
+  GetBookmarksBarChildValue(value.get(), 0, &child1_value);
+  std::wstring title;
+  ASSERT_TRUE(child1_value->GetString(BookmarkCodec::kNameKey, &title));
+  ASSERT_TRUE(child1_value->SetString(BookmarkCodec::kNameKey, title + L"1"));
+
+  std::string dec_checksum;
+  scoped_ptr<BookmarkModel> decoded_model1(DecodeHelper(
+      *value.get(), enc_checksum, &dec_checksum, true));
+
+  // Undo the change and make sure the checksum is same as original.
+  ASSERT_TRUE(child1_value->SetString(BookmarkCodec::kNameKey, title));
+  scoped_ptr<BookmarkModel> decoded_model2(DecodeHelper(
+      *value.get(), enc_checksum, &dec_checksum, false));
+}