Implement ID persistence for bookmarks:

- Bookmark codec now takes in a ctor argument persist_ids
- If it's true, it will serialize IDs of bookmarks when encoding, and
  deserialize already serialized IDs (if present) when decoding.
- During decoding, unique-ify the IDs if they are not unique.
- Add unit tests for all new code.


Coming up in a separate changelist:
- Move ID generation logic to bookmark model, and make it non-static.

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

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

10 files changed, 406 insertions, 67 deletions

diff --git a/chrome/browser/bookmarks/bookmark_codec.cc b/chrome/browser/bookmarks/bookmark_codec.cc
index 5c2f186..da8a999 100644
--- a/chrome/browser/bookmarks/bookmark_codec.cc
+++ b/chrome/browser/bookmarks/bookmark_codec.cc
@@ -13,11 +13,34 @@
 
 using base::Time;
 
+UniqueIDGenerator::UniqueIDGenerator() {
+  Reset();
+}
+
+int UniqueIDGenerator::GetUniqueID(int id) {
+  if (assigned_ids_.find(id) != assigned_ids_.end())
+    id = current_max_ + 1;
+
+  if (id > current_max_)
+    current_max_ = id;
+
+  assigned_ids_.insert(id);
+  return id;
+}
+
+void UniqueIDGenerator::Reset() {
+  current_max_ = 0;
+  assigned_ids_.clear();
+  // 0 should always be considered as an ID that's already generated.
+  assigned_ids_.insert(0);
+}
+
 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::kIdKey = L"id";
 const wchar_t* BookmarkCodec::kTypeKey = L"type";
 const wchar_t* BookmarkCodec::kNameKey = L"name";
 const wchar_t* BookmarkCodec::kDateAddedKey = L"date_added";
@@ -30,6 +53,14 @@ const wchar_t* BookmarkCodec::kTypeFolder = L"folder";
 // Current version of the file.
 static const int kCurrentVersion = 1;
 
+BookmarkCodec::BookmarkCodec()
+    : persist_ids_(false) {
+}
+
+BookmarkCodec::BookmarkCodec(bool persist_ids)
+    : persist_ids_(persist_ids) {
+}
+
 Value* BookmarkCodec::Encode(BookmarkModel* model) {
   return Encode(model->GetBookmarkBarNode(), model->other_node());
 }
@@ -53,15 +84,22 @@ Value* BookmarkCodec::Encode(BookmarkNode* bookmark_bar_node,
 }
 
 bool BookmarkCodec::Decode(BookmarkModel* model, const Value& value) {
+  id_generator_.Reset();
   stored_checksum_.clear();
   InitializeChecksum();
   bool success = DecodeHelper(model, value);
   FinalizeChecksum();
+  BookmarkNode::SetNextId(id_generator_.current_max() + 1);
   return success;
 }
 
 Value* BookmarkCodec::EncodeNode(BookmarkNode* node) {
   DictionaryValue* value = new DictionaryValue();
+  std::string id;
+  if (persist_ids_) {
+    id = IntToString(node->id());
+    value->SetString(kIdKey, id);
+  }
   const std::wstring& title = node->GetTitle();
   value->SetString(kNameKey, title);
   value->SetString(kDateAddedKey,
@@ -70,13 +108,13 @@ Value* BookmarkCodec::EncodeNode(BookmarkNode* node) {
     value->SetString(kTypeKey, kTypeURL);
     std::wstring url = UTF8ToWide(node->GetURL().possibly_invalid_spec());
     value->SetString(kURLKey, url);
-    UpdateChecksumWithUrlNode(title, url);
+    UpdateChecksumWithUrlNode(id, title, url);
   } else {
     value->SetString(kTypeKey, kTypeFolder);
     value->SetString(kDateModifiedKey,
                      Int64ToWString(node->date_group_modified().
                                     ToInternalValue()));
-    UpdateChecksumWithFolderNode(title);
+    UpdateChecksumWithFolderNode(id, title);
 
     ListValue* child_values = new ListValue();
     value->Set(kChildrenKey, child_values);
@@ -162,6 +200,15 @@ bool BookmarkCodec::DecodeNode(BookmarkModel* model,
                                const DictionaryValue& value,
                                BookmarkNode* parent,
                                BookmarkNode* node) {
+  std::string id_string;
+  int id = 0;
+  if (persist_ids_) {
+    if (value.GetString(kIdKey, &id_string))
+      if (!StringToInt(id_string, &id))
+        return false;
+    id = id_generator_.GetUniqueID(id);
+  }
+
   std::wstring title;
   if (!value.GetString(kNameKey, &title))
     return false;
@@ -185,11 +232,15 @@ bool BookmarkCodec::DecodeNode(BookmarkModel* model,
       return false;
     // TODO(sky): this should ignore the node if not a valid URL.
     if (!node)
-      node = new BookmarkNode(model, GURL(WideToUTF8(url_string)));
+      node = new BookmarkNode(model, id, GURL(WideToUTF8(url_string)));
+    else
+      NOTREACHED();  // In case of a URL type node should always be NULL.
+
+
     if (parent)
       parent->Add(parent->GetChildCount(), node);
     node->type_ = history::StarredEntry::URL;
-    UpdateChecksumWithUrlNode(title, url_string);
+    UpdateChecksumWithUrlNode(id_string, title, url_string);
   } else {
     std::wstring last_modified_date;
     if (!value.GetString(kDateModifiedKey, &last_modified_date))
@@ -202,8 +253,15 @@ bool BookmarkCodec::DecodeNode(BookmarkModel* model,
     if (child_values->GetType() != Value::TYPE_LIST)
       return false;
 
-    if (!node)
-      node = new BookmarkNode(model, GURL());
+    if (!node) {
+      node = new BookmarkNode(model, id, GURL());
+    } else if (persist_ids_) {
+      // If a new node is not created, explicitly assign persisted ID to the
+      // existing node.
+      DCHECK(id != 0);
+      node->set_id(id);
+    }
+
     node->type_ = history::StarredEntry::USER_GROUP;
     node->date_group_modified_ = Time::FromInternalValue(
         StringToInt64(WideToUTF16Hack(last_modified_date)));
@@ -211,7 +269,7 @@ bool BookmarkCodec::DecodeNode(BookmarkModel* model,
     if (parent)
       parent->Add(parent->GetChildCount(), node);
 
-    UpdateChecksumWithFolderNode(title);
+    UpdateChecksumWithFolderNode(id_string, title);
     if (!DecodeChildren(model, *static_cast<ListValue*>(child_values), node))
       return false;
   }
@@ -230,14 +288,18 @@ void BookmarkCodec::UpdateChecksum(const std::wstring& str) {
   MD5Update(&md5_context_, str.data(), str.length() * sizeof(wchar_t));
 }
 
-void BookmarkCodec::UpdateChecksumWithUrlNode(const std::wstring& title,
+void BookmarkCodec::UpdateChecksumWithUrlNode(const std::string& id,
+                                              const std::wstring& title,
                                               const std::wstring& url) {
+  UpdateChecksum(id);
   UpdateChecksum(title);
   UpdateChecksum(kTypeURL);
   UpdateChecksum(url);
 }
 
-void BookmarkCodec::UpdateChecksumWithFolderNode(const std::wstring& title) {
+void BookmarkCodec::UpdateChecksumWithFolderNode(const std::string& id,
+                                                 const std::wstring& title) {
+  UpdateChecksum(id);
   UpdateChecksum(title);
   UpdateChecksum(kTypeFolder);
 }
diff --git a/chrome/browser/bookmarks/bookmark_codec.h b/chrome/browser/bookmarks/bookmark_codec.h
index fb9d06f..3af303d 100644
--- a/chrome/browser/bookmarks/bookmark_codec.h
+++ b/chrome/browser/bookmarks/bookmark_codec.h
@@ -9,6 +9,7 @@
 #ifndef CHROME_BROWSER_BOOKMARKS_BOOKMARK_CODEC_H_
 #define CHROME_BROWSER_BOOKMARKS_BOOKMARK_CODEC_H_
 
+#include <set>
 #include <string>
 
 #include "base/basictypes.h"
@@ -20,12 +21,45 @@ class DictionaryValue;
 class ListValue;
 class Value;
 
+// Utility class to help assign unique integer IDs.
+class UniqueIDGenerator {
+ public:
+  UniqueIDGenerator();
+
+  // Checks whether the given ID can be used as a unique ID or not. If it can,
+  // returns the id itself, otherwise generates a new unique id in a simple way
+  // and returns that.
+  // NOTE that if id is 0, a new unique id is returned.
+  int GetUniqueID(int id);
+
+  // Resets the ID generator to initial state.
+  void Reset();
+
+  // Returns the current maximum.
+  int current_max() const { return current_max_; }
+
+ private:
+  // Maximum value we have seen so far.
+  int current_max_;
+  // All IDs assigned so far.
+  std::set<int> assigned_ids_;
+
+  DISALLOW_COPY_AND_ASSIGN(UniqueIDGenerator);
+};
+
 // BookmarkCodec is responsible for encoding/decoding bookmarks into JSON
 // values. BookmarkCodec is used by BookmarkService.
 
 class BookmarkCodec {
  public:
-  BookmarkCodec() {}
+  // Creates an instance of the codec. Encodes/decodes bookmark IDs also if
+  // persist_ids is true. The default constructor will not encode/decode IDs.
+  // During decoding, if persist_ids is true and if the IDs in the file are not
+  // unique, we will reassign IDs to make them unique. There are no guarantees
+  // on how the IDs are reassigned or about doing minimal reassignments to
+  // achieve uniqueness.
+  BookmarkCodec();
+  explicit BookmarkCodec(bool persist_ids);
 
   // Encodes the model to a JSON value. It's up to the caller to delete the
   // returned object. This is invoked to encode the contents of the bookmark bar
@@ -62,6 +96,7 @@ class BookmarkCodec {
   static const wchar_t* kOtherBookmarFolderNameKey;
   static const wchar_t* kVersionKey;
   static const wchar_t* kChecksumKey;
+  static const wchar_t* kIdKey;
   static const wchar_t* kTypeKey;
   static const wchar_t* kNameKey;
   static const wchar_t* kDateAddedKey;
@@ -103,14 +138,21 @@ class BookmarkCodec {
   // 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,
+  void UpdateChecksumWithUrlNode(const std::string& id,
+                                 const std::wstring& title,
                                  const std::wstring& url);
-  void UpdateChecksumWithFolderNode(const std::wstring& title);
+  void UpdateChecksumWithFolderNode(const std::string& id,
+                                    const std::wstring& title);
 
   // Initializes/Finalizes the checksum.
   void InitializeChecksum();
   void FinalizeChecksum();
 
+  // Whether to persist IDs or not.
+  bool persist_ids_;
+  // Unique ID generator used during decoding.
+  UniqueIDGenerator id_generator_;
+
   // MD5 context used to compute MD5 hash of all bookmark data.
   MD5Context md5_context_;
 
@@ -118,7 +160,6 @@ class BookmarkCodec {
   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
index 59e0af5..1b7a4d3 100644
--- a/chrome/browser/bookmarks/bookmark_codec_unittest.cc
+++ b/chrome/browser/bookmarks/bookmark_codec_unittest.cc
@@ -5,26 +5,49 @@
 #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_model.h"
+#include "chrome/browser/bookmarks/bookmark_model_test_utils.h"
 #include "chrome/browser/bookmarks/bookmark_utils.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
+namespace {
+
+const wchar_t kUrl1Title[] = L"url1";
+const wchar_t kUrl1Url[] = L"http://www.url1.com";
+const wchar_t kUrl2Title[] = L"url2";
+const wchar_t kUrl2Url[] = L"http://www.url2.com";
+const wchar_t kUrl3Title[] = L"url3";
+const wchar_t kUrl3Url[] = L"http://www.url3.com";
+const wchar_t kUrl4Title[] = L"url4";
+const wchar_t kUrl4Url[] = L"http://www.url4.com";
+const wchar_t kGroup1Title[] = L"group1";
+const wchar_t kGroup2Title[] = L"group2";
+
+}
+
 class BookmarkCodecTest : public testing::Test {
  protected:
   // Helpers to create bookmark models with different data.
-  // Callers own the returned instances.
-  BookmarkModel* CreateModelWithOneUrl() {
+  BookmarkModel* CreateTestModel1() {
     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, 0, kUrl1Title, GURL(kUrl1Url));
     return model.release();
   }
-  BookmarkModel* CreateModelWithTwoUrls() {
+  BookmarkModel* CreateTestModel2() {
     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"));
+    model->AddURL(bookmark_bar, 0, kUrl1Title, GURL(kUrl1Url));
+    model->AddURL(bookmark_bar, 1, kUrl2Title, GURL(kUrl2Url));
+    return model.release();
+  }
+  BookmarkModel* CreateTestModel3() {
+    scoped_ptr<BookmarkModel> model(new BookmarkModel(NULL));
+    BookmarkNode* bookmark_bar = model->GetBookmarkBarNode();
+    model->AddURL(bookmark_bar, 0, kUrl1Title, GURL(kUrl1Url));
+    BookmarkNode* group1 = model->AddGroup(bookmark_bar, 1, kGroup1Title);
+    model->AddURL(group1, 0, kUrl2Title, GURL(kUrl2Url));
     return model.release();
   }
 
@@ -111,7 +134,7 @@ class BookmarkCodecTest : public testing::Test {
 };
 
 TEST_F(BookmarkCodecTest, ChecksumEncodeDecodeTest) {
-  scoped_ptr<BookmarkModel> model_to_encode(CreateModelWithOneUrl());
+  scoped_ptr<BookmarkModel> model_to_encode(CreateTestModel1());
   std::string enc_checksum;
   scoped_ptr<Value> value(EncodeHelper(model_to_encode.get(), &enc_checksum));
 
@@ -125,12 +148,12 @@ TEST_F(BookmarkCodecTest, ChecksumEncodeDecodeTest) {
 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());
+  scoped_ptr<BookmarkModel> model1(CreateTestModel1());
   std::string enc_checksum1;
   scoped_ptr<Value> value1(EncodeHelper(model1.get(), &enc_checksum1));
   EXPECT_TRUE(value1.get() != NULL);
 
-  scoped_ptr<BookmarkModel> model2(CreateModelWithOneUrl());
+  scoped_ptr<BookmarkModel> model2(CreateTestModel1());
   std::string enc_checksum2;
   scoped_ptr<Value> value2(EncodeHelper(model2.get(), &enc_checksum2));
   EXPECT_TRUE(value2.get() != NULL);
@@ -139,7 +162,7 @@ TEST_F(BookmarkCodecTest, ChecksumEncodeIdenticalModelsTest) {
 }
 
 TEST_F(BookmarkCodecTest, ChecksumManualEditTest) {
-  scoped_ptr<BookmarkModel> model_to_encode(CreateModelWithOneUrl());
+  scoped_ptr<BookmarkModel> model_to_encode(CreateTestModel1());
   std::string enc_checksum;
   scoped_ptr<Value> value(EncodeHelper(model_to_encode.get(), &enc_checksum));
 
@@ -161,3 +184,130 @@ TEST_F(BookmarkCodecTest, ChecksumManualEditTest) {
   scoped_ptr<BookmarkModel> decoded_model2(DecodeHelper(
       *value.get(), enc_checksum, &dec_checksum, false));
 }
+
+TEST_F(BookmarkCodecTest, PersistIDsTest) {
+  scoped_ptr<BookmarkModel> model_to_encode(CreateTestModel3());
+  BookmarkCodec encoder(true);
+  scoped_ptr<Value> model_value(encoder.Encode(model_to_encode.get()));
+
+  // Set the next id to 1 to simulate fresh Chrome start.
+  BookmarkNode::SetNextId(1);
+
+  BookmarkModel decoded_model(NULL);
+  BookmarkCodec decoder(true);
+  ASSERT_TRUE(decoder.Decode(&decoded_model, *model_value.get()));
+  BookmarkModelTestUtils::AssertModelsEqual(model_to_encode.get(),
+                                            &decoded_model,
+                                            true);
+
+  // Add a couple of more items to the decoded bookmark model and make sure
+  // ID persistence is working properly.
+  BookmarkNode* bookmark_bar = decoded_model.GetBookmarkBarNode();
+  decoded_model.AddURL(
+      bookmark_bar, bookmark_bar->GetChildCount(), kUrl3Title, GURL(kUrl3Url));
+  BookmarkNode* group2_node = decoded_model.AddGroup(
+      bookmark_bar, bookmark_bar->GetChildCount(), kGroup2Title);
+  decoded_model.AddURL(group2_node, 0, kUrl4Title, GURL(kUrl4Url));
+
+  BookmarkCodec encoder2(true);
+  scoped_ptr<Value> model_value2(encoder2.Encode(&decoded_model));
+
+  // Set the next id to 1 to simulate fresh Chrome start.
+  BookmarkNode::SetNextId(1);
+
+  BookmarkModel decoded_model2(NULL);
+  BookmarkCodec decoder2(true);
+  ASSERT_TRUE(decoder2.Decode(&decoded_model2, *model_value2.get()));
+  BookmarkModelTestUtils::AssertModelsEqual(&decoded_model,
+                                            &decoded_model2,
+                                            true);
+}
+
+class UniqueIDGeneratorTest : public testing::Test {
+ protected:
+  void TestMixed(UniqueIDGenerator* gen) {
+    // Few unique numbers.
+    for (int i = 1; i <= 5; ++i) {
+      EXPECT_EQ(i, gen->GetUniqueID(i));
+    }
+
+    // All numbers from 1 to 5 should produce numbers 6 to 10.
+    for (int i = 1; i <= 5; ++i) {
+      EXPECT_EQ(5 + i, gen->GetUniqueID(i));
+    }
+
+    // 10 should produce 11, then 11 should produce 12, and so on.
+    for (int i = 1; i <= 5; ++i) {
+      EXPECT_EQ(10 + i, gen->GetUniqueID(9 + i));
+    }
+
+    // Any numbers between 1 and 15 should produce a new numbers in sequence.
+    EXPECT_EQ(16, gen->GetUniqueID(10));
+    EXPECT_EQ(17, gen->GetUniqueID(2));
+    EXPECT_EQ(18, gen->GetUniqueID(14));
+    EXPECT_EQ(19, gen->GetUniqueID(7));
+    EXPECT_EQ(20, gen->GetUniqueID(4));
+
+    // Numbers not yet generated should work.
+    EXPECT_EQ(100, gen->GetUniqueID(100));
+    EXPECT_EQ(21, gen->GetUniqueID(21));
+    EXPECT_EQ(200, gen->GetUniqueID(200));
+
+    // Now any existing number should produce numbers starting from 201.
+    EXPECT_EQ(201, gen->GetUniqueID(1));
+    EXPECT_EQ(202, gen->GetUniqueID(20));
+    EXPECT_EQ(203, gen->GetUniqueID(21));
+    EXPECT_EQ(204, gen->GetUniqueID(100));
+    EXPECT_EQ(205, gen->GetUniqueID(200));
+  }
+};
+
+TEST_F(UniqueIDGeneratorTest, SerialNumbersTest) {
+  UniqueIDGenerator gen;
+  for (int i = 1; i <= 10; ++i) {
+    EXPECT_EQ(i, gen.GetUniqueID(i));
+  }
+}
+
+TEST_F(UniqueIDGeneratorTest, UniquSortedNumbersTest) {
+  UniqueIDGenerator gen;
+  for (int i = 1; i <= 10; i += 2) {
+    EXPECT_EQ(i, gen.GetUniqueID(i));
+  }
+}
+
+TEST_F(UniqueIDGeneratorTest, UniquUnsortedConsecutiveNumbersTest) {
+  UniqueIDGenerator gen;
+  int numbers[] = {2, 10, 6, 3, 8, 5, 1, 7, 4, 9};
+  for (int i = 0; i < ARRAYSIZE(numbers); ++i) {
+    EXPECT_EQ(numbers[i], gen.GetUniqueID(numbers[i]));
+  }
+}
+
+TEST_F(UniqueIDGeneratorTest, UniquUnsortedNumbersTest) {
+  UniqueIDGenerator gen;
+  int numbers[] = {20, 100, 60, 30, 80, 50, 10, 70, 40, 90};
+  for (int i = 0; i < ARRAYSIZE(numbers); ++i) {
+    EXPECT_EQ(numbers[i], gen.GetUniqueID(numbers[i]));
+  }
+}
+
+TEST_F(UniqueIDGeneratorTest, AllDuplicatesTest) {
+  UniqueIDGenerator gen;
+  for (int i = 1; i <= 10; ++i) {
+    EXPECT_EQ(i, gen.GetUniqueID(1));
+  }
+}
+
+TEST_F(UniqueIDGeneratorTest, MixedTest) {
+  UniqueIDGenerator gen;
+  TestMixed(&gen);
+}
+
+TEST_F(UniqueIDGeneratorTest, ResetTest) {
+  UniqueIDGenerator gen;
+  for (int i = 0; i < 5; ++i) {
+    TestMixed(&gen);
+    gen.Reset();
+  }
+}
diff --git a/chrome/browser/bookmarks/bookmark_model.cc b/chrome/browser/bookmarks/bookmark_model.cc
index 6540efe..3bf43dd 100644
--- a/chrome/browser/bookmarks/bookmark_model.cc
+++ b/chrome/browser/bookmarks/bookmark_model.cc
@@ -27,6 +27,11 @@ int next_id_ = 1;
 
 }
 
+// static
+void BookmarkNode::SetNextId(int next_id) {
+  next_id_ = next_id;
+}
+
 const SkBitmap& BookmarkNode::GetFavIcon() {
   if (!loaded_favicon_) {
     loaded_favicon_ = true;
@@ -36,14 +41,23 @@ const SkBitmap& BookmarkNode::GetFavIcon() {
 }
 
 BookmarkNode::BookmarkNode(BookmarkModel* model, const GURL& url)
-    : model_(model),
-      id_(next_id_++),
-      loaded_favicon_(false),
-      favicon_load_handle_(0),
-      url_(url),
-      type_(!url.is_empty() ? history::StarredEntry::URL :
-            history::StarredEntry::BOOKMARK_BAR),
-      date_added_(Time::Now()) {
+    : url_(url) {
+  Initialize(model, 0);
+}
+
+BookmarkNode::BookmarkNode(BookmarkModel* model, int id, const GURL& url)
+    : url_(url){
+  Initialize(model, id);
+}
+
+void BookmarkNode::Initialize(BookmarkModel* model, int id) {
+  model_ = model;
+  id_ = id == 0 ? next_id_++ : id;
+  loaded_favicon_ = false;
+  favicon_load_handle_ = 0;
+  type_ = !url_.is_empty() ? history::StarredEntry::URL :
+          history::StarredEntry::BOOKMARK_BAR;
+  date_added_ = Time::Now();
 }
 
 void BookmarkNode::Reset(const history::StarredEntry& entry) {
diff --git a/chrome/browser/bookmarks/bookmark_model.h b/chrome/browser/bookmarks/bookmark_model.h
index 5f63b73..b5ad92a 100644
--- a/chrome/browser/bookmarks/bookmark_model.h
+++ b/chrome/browser/bookmarks/bookmark_model.h
@@ -43,13 +43,17 @@ class BookmarkNode : public views::TreeNode<BookmarkNode> {
   friend class BookmarkModel;
   friend class BookmarkCodec;
   friend class history::StarredURLDatabase;
+  FRIEND_TEST(BookmarkCodecTest, PersistIDsTest);
   FRIEND_TEST(BookmarkEditorViewTest, ChangeParentAndURL);
   FRIEND_TEST(BookmarkEditorViewTest, EditURLKeepsPosition);
   FRIEND_TEST(BookmarkModelTest, MostRecentlyAddedEntries);
   FRIEND_TEST(BookmarkModelTest, GetMostRecentlyAddedNodeForURL);
 
  public:
+  // Creates a new node with the given properties. If the ID is not given or is
+  // 0, it is automatically assigned.
   BookmarkNode(BookmarkModel* model, const GURL& url);
+  BookmarkNode(BookmarkModel* model, int id, const GURL& url);
   virtual ~BookmarkNode() {}
 
   // Returns the favicon for the this node. If the favicon has not yet been
@@ -92,14 +96,23 @@ class BookmarkNode : public views::TreeNode<BookmarkNode> {
   // HistoryContentsProvider.
 
  private:
+  // Sets the next ID for bookmark node ID generation.
+  static void SetNextId(int next_id);
+
+  // helper to initialize various fields during construction.
+  void Initialize(BookmarkModel* model, int id);
+
   // Resets the properties of the node from the supplied entry.
   void Reset(const history::StarredEntry& entry);
 
+  // Sets the id to the given value.
+  void set_id(int id) { id_ = id; }
+
   // The model. This is NULL when created by StarredURLDatabase for migration.
   BookmarkModel* model_;
 
   // Unique identifier for this node.
-  const int id_;
+  int id_;
 
   // Whether the favicon has been loaded.
   bool loaded_favicon_;
diff --git a/chrome/browser/bookmarks/bookmark_model_test_utils.cc b/chrome/browser/bookmarks/bookmark_model_test_utils.cc
new file mode 100644
index 0000000..004bf51
--- /dev/null
+++ b/chrome/browser/bookmarks/bookmark_model_test_utils.cc
@@ -0,0 +1,43 @@
+// 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 "chrome/browser/bookmarks/bookmark_model_test_utils.h"
+
+#include "chrome/browser/bookmarks/bookmark_model.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// static
+void BookmarkModelTestUtils::AssertNodesEqual(BookmarkNode* expected,
+                                              BookmarkNode* actual,
+                                              bool check_ids) {
+  ASSERT_TRUE(expected);
+  ASSERT_TRUE(actual);
+  if (check_ids)
+    EXPECT_EQ(expected->id(), actual->id());
+  EXPECT_EQ(expected->GetTitle(), actual->GetTitle());
+  EXPECT_EQ(expected->GetType(), actual->GetType());
+  EXPECT_TRUE(expected->date_added() == actual->date_added());
+  if (expected->GetType() == history::StarredEntry::URL) {
+    EXPECT_EQ(expected->GetURL(), actual->GetURL());
+  } else {
+    EXPECT_TRUE(expected->date_group_modified() ==
+                actual->date_group_modified());
+    ASSERT_EQ(expected->GetChildCount(), actual->GetChildCount());
+    for (int i = 0; i < expected->GetChildCount(); ++i)
+      AssertNodesEqual(expected->GetChild(i), actual->GetChild(i), check_ids);
+  }
+}
+
+// static
+void BookmarkModelTestUtils::AssertModelsEqual(BookmarkModel* expected,
+                                               BookmarkModel* actual,
+                                               bool check_ids) {
+  AssertNodesEqual(expected->GetBookmarkBarNode(),
+                   actual->GetBookmarkBarNode(),
+                   check_ids);
+  AssertNodesEqual(expected->other_node(),
+                   actual->other_node(),
+                   check_ids);
+}
+
diff --git a/chrome/browser/bookmarks/bookmark_model_test_utils.h b/chrome/browser/bookmarks/bookmark_model_test_utils.h
new file mode 100644
index 0000000..fbd814f
--- /dev/null
+++ b/chrome/browser/bookmarks/bookmark_model_test_utils.h
@@ -0,0 +1,27 @@
+// 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.
+
+#ifndef CHROME_BROWSER_BOOKMARKS_BOOKMARK_MODEL_TEST_UTILS_H_
+#define CHROME_BROWSER_BOOKMARKS_BOOKMARK_MODEL_TEST_UTILS_H_
+
+class BookmarkModel;
+class BookmarkNode;
+
+// Contains utilities for bookmark model related tests.
+class BookmarkModelTestUtils {
+ public:
+  // Verifies that the two given bookmark models are the same.
+  // The IDs of the bookmark nodes are compared only if check_ids is true.
+  static void AssertModelsEqual(BookmarkModel* expected,
+                                BookmarkModel* actual,
+                                bool check_ids);
+ private:
+  // Helper to verify the two given bookmark nodes.
+  // The IDs of the bookmark nodes are compared only if check_ids is true.
+  static void AssertNodesEqual(BookmarkNode* expected,
+                               BookmarkNode* actual,
+                               bool check_ids);
+};
+
+#endif  // CHROME_BROWSER_BOOKMARKS_BOOKMARK_MODEL_TEST_UTILS_H_
diff --git a/chrome/browser/bookmarks/bookmark_model_unittest.cc b/chrome/browser/bookmarks/bookmark_model_unittest.cc
index 09b14bb..40edbb8 100644
--- a/chrome/browser/bookmarks/bookmark_model_unittest.cc
+++ b/chrome/browser/bookmarks/bookmark_model_unittest.cc
@@ -3,8 +3,8 @@
 // found in the LICENSE file.
 
 #include "base/string_util.h"
-#include "chrome/browser/bookmarks/bookmark_model.h"
 #include "chrome/browser/bookmarks/bookmark_codec.h"
+#include "chrome/browser/bookmarks/bookmark_model.h"
 #include "chrome/browser/bookmarks/bookmark_utils.h"
 #include "chrome/common/chrome_constants.h"
 #include "chrome/common/chrome_paths.h"
@@ -118,31 +118,6 @@ class BookmarkModelTest : public testing::Test, public BookmarkModelObserver {
     ASSERT_EQ(reordered_count, reordered_count_);
   }
 
-  void AssertNodesEqual(BookmarkNode* expected, BookmarkNode* actual) {
-    ASSERT_TRUE(expected);
-    ASSERT_TRUE(actual);
-    EXPECT_EQ(expected->GetTitle(), actual->GetTitle());
-    EXPECT_EQ(expected->GetType(), actual->GetType());
-    EXPECT_TRUE(expected->date_added() == actual->date_added());
-    if (expected->GetType() == history::StarredEntry::URL) {
-      EXPECT_EQ(expected->GetURL(), actual->GetURL());
-    } else {
-      EXPECT_TRUE(expected->date_group_modified() ==
-                  actual->date_group_modified());
-      ASSERT_EQ(expected->GetChildCount(), actual->GetChildCount());
-      for (int i = 0; i < expected->GetChildCount(); ++i)
-        AssertNodesEqual(expected->GetChild(i), actual->GetChild(i));
-    }
-  }
-
-  void AssertModelsEqual(BookmarkModel* expected,
-                         BookmarkModel* actual) {
-    AssertNodesEqual(expected->GetBookmarkBarNode(),
-                     actual->GetBookmarkBarNode());
-    AssertNodesEqual(expected->other_node(),
-                     actual->other_node());
-  }
-
   BookmarkModel model;
 
   int moved_count;
diff --git a/chrome/chrome.gyp b/chrome/chrome.gyp
index 3013a11..39c45a3 100644
--- a/chrome/chrome.gyp
+++ b/chrome/chrome.gyp
@@ -2244,6 +2244,8 @@
         'browser/bookmarks/bookmark_drag_data_unittest.cc',
         'browser/bookmarks/bookmark_folder_tree_model_unittest.cc',
         'browser/bookmarks/bookmark_html_writer_unittest.cc',
+        'browser/bookmarks/bookmark_model_test_utils.cc',
+        'browser/bookmarks/bookmark_model_test_utils.h',
         'browser/bookmarks/bookmark_model_unittest.cc',
         'browser/bookmarks/bookmark_table_model_unittest.cc',
         'browser/bookmarks/bookmark_utils_unittest.cc',
diff --git a/chrome/test/unit/unittests.vcproj b/chrome/test/unit/unittests.vcproj
index 0dc8102..ad63a8b 100644
--- a/chrome/test/unit/unittests.vcproj
+++ b/chrome/test/unit/unittests.vcproj
@@ -400,6 +400,10 @@
 				>
 			</File>
 			<File
+				RelativePath="..\..\browser\bookmarks\bookmark_codec_unittest.cc"
+				>
+			</File>
+			<File
 				RelativePath="..\..\browser\bookmarks\bookmark_context_menu_test.cc"
 				>
 			</File>
@@ -420,6 +424,14 @@
 				>
 			</File>
 			<File
+				RelativePath="..\..\browser\bookmarks\bookmark_model_test_utils.cc"
+				>
+			</File>
+			<File
+				RelativePath="..\..\browser\bookmarks\bookmark_model_test_utils.h"
+				>
+			</File>
+			<File
 				RelativePath="..\..\browser\bookmarks\bookmark_model_unittest.cc"
 				>
 			</File>
@@ -564,10 +576,6 @@
 				>
 			</File>
 			<File
-				RelativePath="..\..\browser\autocomplete\search_provider_unittest.cc"
-				>
-			</File>
-			<File
 				RelativePath="..\..\browser\login_prompt_unittest.cc"
 				>
 			</File>
@@ -680,6 +688,10 @@
 				>
 			</File>
 			<File
+				RelativePath="..\..\browser\autocomplete\search_provider_unittest.cc"
+				>
+			</File>
+			<File
 				RelativePath="..\..\browser\sessions\session_backend_unittest.cc"
 				>
 			</File>
@@ -847,19 +859,19 @@
 					>
 				</File>
 				<File
-					RelativePath="..\..\browser\net\test_url_fetcher_factory.cc"
+					RelativePath="..\..\browser\renderer_host\test_render_view_host.cc"
 					>
 				</File>
 				<File
-					RelativePath="..\..\browser\net\test_url_fetcher_factory.h"
+					RelativePath="..\..\browser\renderer_host\test_render_view_host.h"
 					>
 				</File>
 				<File
-					RelativePath="..\..\browser\renderer_host\test_render_view_host.cc"
+					RelativePath="..\..\browser\net\test_url_fetcher_factory.cc"
 					>
 				</File>
 				<File
-					RelativePath="..\..\browser\renderer_host\test_render_view_host.h"
+					RelativePath="..\..\browser\net\test_url_fetcher_factory.h"
 					>
 				</File>
 				<File