Convert app_launch_index and page_index from int to StringOrdinal.

chrome/browser/extensions/extension_prefs.cc

Index: chrome/browser/extensions/extension_prefs.cc
diff --git a/chrome/browser/extensions/extension_prefs.cc b/chrome/browser/extensions/extension_prefs.cc
index 92412645bc76dc65f1c8531c4d385367bb72c0f3..455227f22dc090e742a076a9fca9d0e7244edff5 100644
--- a/chrome/browser/extensions/extension_prefs.cc
+++ b/chrome/browser/extensions/extension_prefs.cc
@@ -110,10 +110,12 @@ const char kWebStoreLogin[] = "extensions.webstore_login";
 const char kPrefLaunchType[] = "launchType";
 
 // A preference determining the order of which the apps appear on the NTP.
-const char kPrefAppLaunchIndex[] = "app_launcher_index";
+const char kPrefAppLaunchIndexDeprecated[] = "app_launcher_index";
+const char kPrefAppLaunchIndex[] = "app_launcher_index_string_ordinal";
 
 // A preference determining the page on which an app appears in the NTP.
-const char kPrefPageIndex[] = "page_index";
+const char kPrefPageIndexDeprecated[] = "page_index";
+const char kPrefPageIndex[] = "page_index_string_ordinal";
 
 // A preference specifying if the user dragged the app on the NTP.
 const char kPrefUserDraggedApp[] = "user_dragged_app_ntp";
@@ -239,6 +241,30 @@ std::string JoinPrefs(std::string parent, const char* child) {
   return parent + "." + child;
 }
 
+// A simple structure used when sorting applications based on the order they
+// appear on the NTP. This is used by the code that migrates the data
+// from integers to StringOrdinals.
+struct ApplicationNTPOldPosition {
+  const std::string* application_id;
+  const int page_index;
+  const int app_launch_index;
+
+  ApplicationNTPOldPosition(const std::string& app_id, int page, int app_launch)
+      : application_id(&app_id),
+        page_index(page),
+        app_launch_index(app_launch) {}
+};
+
+struct SortByNTPOldPosition {
+  bool operator() (const ApplicationNTPOldPosition& lhs,
+                   const ApplicationNTPOldPosition& rhs) const {
+    if (lhs.page_index != rhs.page_index)
+      return lhs.page_index < rhs.page_index;
+
+    return lhs.app_launch_index < rhs.app_launch_index;
+  }
+};
+
 }  // namespace
 
 ExtensionPrefs::ExtensionPrefs(
@@ -415,6 +441,17 @@ bool ExtensionPrefs::ReadExtensionPrefList(
   return true;
 }
 
+bool ExtensionPrefs::ReadExtensionPrefString(
+    const std::string& extension_id, const std::string& pref_key,
+    std::string* out_value) const {
+  const DictionaryValue* ext = GetExtensionPref(extension_id);
+
+  if (!ext || !ext->GetString(pref_key, out_value))
+    return false;
+
+  return true;
+}
+
 bool ExtensionPrefs::ReadExtensionPrefURLPatternSet(
     const std::string& extension_id,
     const std::string& pref_key,
@@ -858,6 +895,63 @@ void ExtensionPrefs::MigratePermissions(const ExtensionIdSet& extension_ids) {
   }
 }
 
+void ExtensionPrefs::MigrateAppIndex(const ExtensionIdSet& extension_ids) {
+  if (extension_ids.begin() == extension_ids.end())
+    return;
+
+  // Create a sorted set of all the extensions that need either their page
+  // or launch index converted.
+  std::set<ApplicationNTPOldPosition, SortByNTPOldPosition> apps_to_convert;
+  for (ExtensionIdSet::const_iterator ext_id = extension_ids.begin();
+       ext_id != extension_ids.end(); ++ext_id) {
+    int old_page_index = 0;
+    int old_app_launch_index = 0;
+
+    bool has_old_values = ReadExtensionPrefInteger(*ext_id,
+                                                   kPrefPageIndexDeprecated,
+                                                   &old_page_index);
+    has_old_values |= ReadExtensionPrefInteger(*ext_id,
+                                               kPrefAppLaunchIndexDeprecated,
+                                               &old_app_launch_index);
+
+    if (has_old_values) {
+      // Its ok to use both values, even if they weren't read, because this
+      // only affects the sorting, which can handle apps with the default
+      // integer values.
+      apps_to_convert.insert(ApplicationNTPOldPosition(
+          *ext_id, old_page_index, old_app_launch_index));
+    }
+  }
+
+  if (apps_to_convert.empty())
+    return;
+
+  // Create the new values and remove the old preferences.
+  for (std::set<ApplicationNTPOldPosition, SortByNTPOldPosition>::iterator ext =
+           apps_to_convert.begin(); ext != apps_to_convert.end(); ++ext) {
+    int old_page_index;
+    if (ReadExtensionPrefInteger(*(ext->application_id),
+                                 kPrefPageIndexDeprecated,
+                                 &old_page_index)) {
+      SetPageIndex(*(ext->application_id),
+                   PageIndexAsStringOrdinal(old_page_index));
+      UpdateExtensionPref(
+          *(ext->application_id), kPrefPageIndexDeprecated, NULL);
+    }
+
+    int old_app_launch_index;
+    if (ReadExtensionPrefInteger(*(ext->application_id),
+                                 kPrefAppLaunchIndexDeprecated,
+                                 &old_app_launch_index)) {
+      StringOrdinal page = GetPageIndex(*(ext->application_id));
+      SetAppLaunchIndex(*(ext->application_id),
+                        GetNextAppLaunchIndex(page));
+      UpdateExtensionPref(
+          *(ext->application_id), kPrefAppLaunchIndexDeprecated, NULL);
+    }
+  }
+}
+
 ExtensionPermissionSet* ExtensionPrefs::GetGrantedPermissions(
     const std::string& extension_id) {
   CHECK(Extension::IdIsValid(extension_id));
@@ -1072,7 +1166,7 @@ void ExtensionPrefs::OnExtensionInstalled(
     const Extension* extension,
     Extension::State initial_state,
     bool from_webstore,
-    int page_index) {
+    StringOrdinal page_index) {
   const std::string& id = extension->id();
   CHECK(Extension::IdIsValid(id));
   ScopedExtensionPrefUpdate update(prefs_, id);
@@ -1104,12 +1198,15 @@ void ExtensionPrefs::OnExtensionInstalled(
   }
 
   if (extension->is_app()) {
-    if (page_index == -1)
+    if (!page_index.IsValid())
       page_index = GetNaturalAppPageIndex();
     extension_dict->Set(kPrefPageIndex,
-                        Value::CreateIntegerValue(page_index));
+                        Value::CreateStringValue(page_index.ToString()));
+    UpdatePageIndexMap(StringOrdinal(), page_index);
+
     extension_dict->Set(kPrefAppLaunchIndex,
-        Value::CreateIntegerValue(GetNextAppLaunchIndex(page_index)));
+                        Value::CreateStringValue(
+                            GetNextAppLaunchIndex(page_index).ToString()));
   }
   extension_pref_value_map_->RegisterExtension(
       id, install_time, initial_state == Extension::ENABLED);
@@ -1442,59 +1539,125 @@ void ExtensionPrefs::SetWebStoreLogin(const std::string& login) {
   SavePrefs();
 }
 
-int ExtensionPrefs::GetAppLaunchIndex(const std::string& extension_id) {
-  int value;
-  if (ReadExtensionPrefInteger(extension_id, kPrefAppLaunchIndex, &value))
-    return value;
+void ExtensionPrefs::GetAllAppLaunchIndicesOnPageSorted(
+    const StringOrdinal& target_page_index,
+    std::set<StringOrdinal, StringOrdinalLessThan>* indices_on_page) const {
+  const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
+  if (!extensions || !target_page_index.IsValid())
+    return;
+
+  for (DictionaryValue::key_iterator ext_it = extensions->begin_keys();
+       ext_it != extensions->end_keys(); ++ext_it) {
+    StringOrdinal page_index = GetPageIndex(*ext_it);
+    if (page_index.IsValid() && page_index.Equal(target_page_index)) {
+      StringOrdinal app_launch_index = GetAppLaunchIndex(*ext_it);
+      if (app_launch_index.IsValid())
+        indices_on_page->insert(app_launch_index);
+    }
+  }
+}
+
+StringOrdinal ExtensionPrefs::GetFirstAppPage() const {
+  const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
+  if (!extensions)
+    return StringOrdinal();
+
+  if (page_index_map_.size() == 0)
+    return StringOrdinal::CreateInitialOrdinal();
 
-  return -1;
+  return page_index_map_.begin()->first;
+}
+
+StringOrdinal ExtensionPrefs::CreateFirstAppLaunchIndex(
+    const StringOrdinal& page_index) const {
+  std::set<StringOrdinal, StringOrdinalLessThan> apps_on_page;
+  GetAllAppLaunchIndicesOnPageSorted(page_index, &apps_on_page);
+
+  if (apps_on_page.empty())
+    return StringOrdinal::CreateInitialOrdinal();
+  else
+    return apps_on_page.begin()->CreateBefore();
+}
+
+StringOrdinal ExtensionPrefs::GetAppLaunchIndex(
+    const std::string& extension_id) const {
+  std::string raw_value;
+  // If the preference read fails then raw_value will still be unset and we
+  // will return an invalid StringOrdinal to signal that no app launch index
+  // was found.
+  ReadExtensionPrefString(extension_id, kPrefAppLaunchIndex, &raw_value);
+  return StringOrdinal(raw_value);
 }
 
 void ExtensionPrefs::SetAppLaunchIndex(const std::string& extension_id,
-                                       int index) {
+                                       const StringOrdinal& index) {
   UpdateExtensionPref(extension_id, kPrefAppLaunchIndex,
-                      Value::CreateIntegerValue(index));
+                      Value::CreateStringValue(index.ToString()));
 }
 
-int ExtensionPrefs::GetNextAppLaunchIndex(int on_page) {
-  const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
-  if (!extensions)
-    return 0;
+StringOrdinal ExtensionPrefs::GetNextAppLaunchIndex(
+    const StringOrdinal& on_page) const {
+  std::set<StringOrdinal, StringOrdinalLessThan> apps_on_page;
+  GetAllAppLaunchIndicesOnPageSorted(on_page, &apps_on_page);
 
-  int max_value = -1;
-  for (DictionaryValue::key_iterator extension_id = extensions->begin_keys();
-       extension_id != extensions->end_keys(); ++extension_id) {
-    int value = GetAppLaunchIndex(*extension_id);
-    int page = GetPageIndex(*extension_id);
-    if (page == on_page && value > max_value)
-      max_value = value;
-  }
-  return max_value + 1;
+  if (apps_on_page.empty())
+    return StringOrdinal::CreateInitialOrdinal();
+  else
+    return apps_on_page.rbegin()->CreateAfter();
 }
 
-int ExtensionPrefs::GetNaturalAppPageIndex() {
+StringOrdinal ExtensionPrefs::GetNaturalAppPageIndex() const {
   const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
   if (!extensions)
-    return 0;
+    return StringOrdinal();
 
-  std::map<int, int> page_counts;
-  for (DictionaryValue::key_iterator extension_id = extensions->begin_keys();
-       extension_id != extensions->end_keys(); ++extension_id) {
-    int page_index = GetPageIndex(*extension_id);
-    if (page_index >= 0)
-      page_counts[page_index] = page_counts[page_index] + 1;
-  }
-  for (int i = 0; ; i++) {
-    std::map<int, int>::const_iterator it = page_counts.find(i);
-    if (it == page_counts.end() || it->second < kNaturalAppPageSize)
-      return i;
+  if (page_index_map_.size() == 0)
+    return StringOrdinal::CreateInitialOrdinal();
+
+  std::map<StringOrdinal, int>::const_iterator it = page_index_map_.begin();
+  for (; it != page_index_map_.end(); ++it) {
+    if (it->second < kNaturalAppPageSize)
+      return it->first;
   }
+
+  // Add a new page as all existing pages are full.
+  StringOrdinal last_element = page_index_map_.rbegin()->first;
+  return last_element.CreateAfter();
 }
 
 void ExtensionPrefs::SetAppLauncherOrder(
-    const std::vector<std::string>& extension_ids) {
-  for (size_t i = 0; i < extension_ids.size(); ++i)
-    SetAppLaunchIndex(extension_ids.at(i), i);
+    const std::vector<std::string>& extension_ids,
+    const std::string& moved_extension_id) {
+  std::vector<std::string>::const_iterator it =
+      find(extension_ids.begin(), extension_ids.end(), moved_extension_id);
+  size_t position = std::distance(extension_ids.begin(), it);
+
+  // We need at least 2 apps for the moved apps old value to be invalidated.
+  if (extension_ids.size() >= 2) {
+    if (position == 0U) {
+      // The app is moving to the start of the group, so we need to get the
+      // previous first StringOrdinal and create the new value before it.
+      ++it;
+      SetAppLaunchIndex(moved_extension_id,
+                        GetAppLaunchIndex(*it).CreateBefore());
+    } else if (position == extension_ids.size() - 1U) {
+      // The app is moving to the end of the group, so we need to get the
+      // previous last StringOrdinal and create the new value after it.
+      --it;
+      SetAppLaunchIndex(moved_extension_id,
+                        GetAppLaunchIndex(*it).CreateAfter());
+    } else {
+      // The app is going into a middle position, which means there are valid
+      // StringOrdinals before and after it. We get the new adjacent
+      // StringOrdinals and create our new value between them.
+      ++it;
+      StringOrdinal value_after = GetAppLaunchIndex(*it);
+      advance(it, -2);
+      StringOrdinal value_before = GetAppLaunchIndex(*it);
+      SetAppLaunchIndex(moved_extension_id,
+                        value_before.CreateBetween(value_after));
+    }
+  }
 
   content::NotificationService::current()->Notify(
       chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
@@ -1502,21 +1665,85 @@ void ExtensionPrefs::SetAppLauncherOrder(
       content::NotificationService::NoDetails());
 }
 
-int ExtensionPrefs::GetPageIndex(const std::string& extension_id) {
-  int value = -1;
-  ReadExtensionPrefInteger(extension_id, kPrefPageIndex, &value);
-  return value;
+StringOrdinal ExtensionPrefs::GetPageIndex(const std::string& extension_id)
+    const {
+  std::string raw_data;
+  // If the preference read fails then raw_value will still be unset and we will
+  // return an invalid StringOrdinal to signal that no page index was found.
+  ReadExtensionPrefString(extension_id, kPrefPageIndex, &raw_data);
+  return StringOrdinal(raw_data);
 }
 
-void ExtensionPrefs::SetPageIndex(const std::string& extension_id, int index) {
+void ExtensionPrefs::SetPageIndex(const std::string& extension_id,
+                                  const StringOrdinal& page_index) {
+  UpdatePageIndexMap(GetPageIndex(extension_id), page_index);
   UpdateExtensionPref(extension_id, kPrefPageIndex,
-                      Value::CreateIntegerValue(index));
+                      Value::CreateStringValue(page_index.ToString()));
 }
 
 void ExtensionPrefs::ClearPageIndex(const std::string& extension_id) {
+  UpdatePageIndexMap(GetPageIndex(extension_id), StringOrdinal());
   UpdateExtensionPref(extension_id, kPrefPageIndex, NULL);
 }
 
+void ExtensionPrefs::InitializePageIndexMap(
+    const ExtensionIdSet& extension_ids) {
+  for (ExtensionIdSet::const_iterator ext_it = extension_ids.begin();
+       ext_it != extension_ids.end(); ++ext_it) {
+    UpdatePageIndexMap(StringOrdinal(), GetPageIndex(*ext_it));
+  }
+}
+
+void ExtensionPrefs::UpdatePageIndexMap(const StringOrdinal& old_value,
+                                        const StringOrdinal& new_value) {
+  if (new_value.IsValid())
+    ++page_index_map_[new_value];
+
+  if (old_value.IsValid()) {
+    --page_index_map_[old_value];
+
+    if (page_index_map_[old_value] == 0)
+      page_index_map_.erase(old_value);
+  }
+}
+
+int ExtensionPrefs::PageIndexAsInteger(const StringOrdinal& page_index) const {
+  if (!page_index.IsValid())
+    return -1;
+
+  std::map<StringOrdinal, int>::const_iterator it =
+      page_index_map_.find(page_index);
+  if (it != page_index_map_.end()) {
+    return std::distance(page_index_map_.begin(), it);
+  } else {
+    return -1;
+  }
+}
+
+StringOrdinal ExtensionPrefs::PageIndexAsStringOrdinal(size_t page_index) {
+  const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
+  if (!extensions)
+    return StringOrdinal();
+
+  if (page_index_map_.size() == 0)
+    return StringOrdinal::CreateInitialOrdinal();
+
+  if (page_index < page_index_map_.size()) {
+    std::map<StringOrdinal, int, StringOrdinalLessThan>::const_iterator it =
+        page_index_map_.begin();
+    advance(it, page_index);
+
+    return it->first;
+  } else {
+    // Create new pages until we reach the desired index.
+    while (page_index >= page_index_map_.size()) {
+      StringOrdinal new_page = page_index_map_.rbegin()->first.CreateAfter();
+      page_index_map_[new_page] = 0;
+    }
+    return page_index_map_.rbegin()->first;
+  }
+}
+
 bool ExtensionPrefs::WasAppDraggedByUser(const std::string& extension_id) {
   return ReadExtensionPrefBoolean(extension_id, kPrefUserDraggedApp);
 }
@@ -1661,7 +1888,9 @@ void ExtensionPrefs::InitPrefStore(bool extensions_disabled) {
   }
 
   FixMissingPrefs(extension_ids);
+  InitializePageIndexMap(extension_ids);
   MigratePermissions(extension_ids);
+  MigrateAppIndex(extension_ids);
 
   // Store extension controlled preference values in the
   // |extension_pref_value_map_|, which then informs the subscribers