Convert app_launch_index and page_index from int to StringOrdinal.

This application icon index values are being changed from ints to StringOrdinals to decrease the potential number of syncs required when icons are moved, by only needing to change 1 StringOrdinal instead of all the integers. This include extra data verification that helps prevent an out of memory crash present in the earlier submission attempt.


BUG=61447,107376
TEST=Open up an instance of chromium with multiple application icons and ensure
that icons can still have their page and order changed. There should be no
behaviour change.


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

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

1 files changed, 300 insertions, 61 deletions

diff --git a/chrome/browser/extensions/extension_prefs.cc b/chrome/browser/extensions/extension_prefs.cc
index 0cd7c90..4357981 100644
--- a/chrome/browser/extensions/extension_prefs.cc
+++ b/chrome/browser/extensions/extension_prefs.cc
@@ -111,10 +111,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 kPrefAppLaunchOrdinal[] = "app_launcher_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 kPrefPageOrdinal[] = "page_ordinal";
 
 // A preference specifying if the user dragged the app on the NTP.
 const char kPrefUserDraggedApp[] = "user_dragged_app_ntp";
@@ -417,6 +419,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,
@@ -864,6 +877,99 @@ void ExtensionPrefs::MigratePermissions(const ExtensionIdSet& extension_ids) {
   }
 }
 
+void ExtensionPrefs::MigrateAppIndex(const ExtensionIdSet& extension_ids) {
+  if (extension_ids.empty())
+    return;
+
+  // Convert all the page index values to page ordinals. If there are any
+  // app launch values that need to be migrated, inserted them into a sorted
+  // set to be dealt with later.
+  typedef std::map<StringOrdinal, std::map<int, const std::string*>,
+      StringOrdinalLessThan> AppPositionToIdMapping;
+  AppPositionToIdMapping app_launches_to_convert;
+  for (ExtensionIdSet::const_iterator ext_id = extension_ids.begin();
+       ext_id != extension_ids.end(); ++ext_id) {
+    int old_page_index = 0;
+    StringOrdinal page = GetPageOrdinal(*ext_id);
+    if (ReadExtensionPrefInteger(*ext_id,
+                                 kPrefPageIndexDeprecated,
+                                 &old_page_index)) {
+      // Some extensions have invalid page index, so we don't
+      // attempt to convert them.
+      if (old_page_index < 0) {
+        DLOG(WARNING) << "Extension " << *ext_id
+                      << " has an invalid page index " << old_page_index
+                      << ". Aborting attempt to convert its index.";
+        break;
+      }
+
+      // Since we require all earlier StringOrdinals to already exist in order
+      // to properly convert from integers and we are iterating though them in
+      // no given order, we create earlier StringOrdinal values as required.
+      // This should be filled in by the time we are done with this loop.
+      if (page_ordinal_map_.empty())
+        page_ordinal_map_[StringOrdinal::CreateInitialOrdinal()] = 0;
+      while (page_ordinal_map_.size() <= static_cast<size_t>(old_page_index)) {
+        StringOrdinal earlier_page =
+            page_ordinal_map_.rbegin()->first.CreateAfter();
+        page_ordinal_map_[earlier_page] = 0;
+      }
+
+      page = PageIntegerAsStringOrdinal(old_page_index);
+      SetPageOrdinal(*ext_id, page);
+      UpdateExtensionPref(*ext_id, kPrefPageIndexDeprecated, NULL);
+    }
+
+    int old_app_launch_index = 0;
+    if (ReadExtensionPrefInteger(*ext_id,
+                                 kPrefAppLaunchIndexDeprecated,
+                                 &old_app_launch_index)) {
+      // We can't update the app launch index value yet, because we use
+      // GetNextAppLaunchOrdinal to get the new ordinal value and it requires
+      // all the ordinals with lower values to have already been migrated.
+      // A valid page ordinal is also required because otherwise there is
+      // no page to add the app to.
+      if (page.IsValid())
+        app_launches_to_convert[page][old_app_launch_index] = &*ext_id;
+
+      UpdateExtensionPref(*ext_id, kPrefAppLaunchIndexDeprecated, NULL);
+    }
+  }
+
+  // Remove any empty pages that may have been added. This shouldn't occur,
+  // but double check here to prevent future problems with conversions between
+  // integers and StringOrdinals.
+  for (PageOrdinalMap::iterator it = page_ordinal_map_.begin();
+       it != page_ordinal_map_.end();) {
+    if (it->second == 0) {
+      PageOrdinalMap::iterator prev_it = it;
+      ++it;
+      page_ordinal_map_.erase(prev_it);
+    } else {
+      ++it;
+    }
+  }
+
+  if (app_launches_to_convert.empty())
+    return;
+
+  // Create the new app launch ordinals and remove the old preferences. Since
+  // the set is sorted, each time we migrate an apps index, we know that all of
+  // the remaining apps will appear further down the NTP than it or on a
+  // different page.
+  for (AppPositionToIdMapping::const_iterator page_it =
+           app_launches_to_convert.begin();
+       page_it != app_launches_to_convert.end(); ++page_it) {
+    StringOrdinal page = page_it->first;
+    for (std::map<int, const std::string*>::const_iterator launch_it =
+            page_it->second.begin(); launch_it != page_it->second.end();
+        ++launch_it) {
+      SetAppLaunchOrdinal(*(launch_it->second),
+                          CreateNextAppLaunchOrdinal(page));
+    }
+  }
+}
+
 ExtensionPermissionSet* ExtensionPrefs::GetGrantedPermissions(
     const std::string& extension_id) {
   CHECK(Extension::IdIsValid(extension_id));
@@ -1079,7 +1185,7 @@ void ExtensionPrefs::OnExtensionInstalled(
     const Extension* extension,
     Extension::State initial_state,
     bool from_webstore,
-    int page_index) {
+    const StringOrdinal& page_ordinal) {
   const std::string& id = extension->id();
   CHECK(Extension::IdIsValid(id));
   ScopedExtensionPrefUpdate update(prefs_, id);
@@ -1111,13 +1217,12 @@ void ExtensionPrefs::OnExtensionInstalled(
   }
 
   if (extension->is_app()) {
-    if (page_index == -1)
-      page_index = GetNaturalAppPageIndex();
-    extension_dict->Set(kPrefPageIndex,
-                        Value::CreateIntegerValue(page_index));
-    extension_dict->Set(kPrefAppLaunchIndex,
-        Value::CreateIntegerValue(GetNextAppLaunchIndex(page_index)));
+    StringOrdinal new_page_ordinal =
+        page_ordinal.IsValid() ? page_ordinal : GetNaturalAppPageOrdinal();
+    SetPageOrdinal(id, new_page_ordinal);
+    SetAppLaunchOrdinal(id, CreateNextAppLaunchOrdinal(new_page_ordinal));
   }
+
   extension_pref_value_map_->RegisterExtension(
       id, install_time, initial_state == Extension::ENABLED);
   content_settings_store_->RegisterExtension(
@@ -1142,6 +1247,37 @@ void ExtensionPrefs::OnExtensionUninstalled(const std::string& extension_id,
   }
 }
 
+void ExtensionPrefs::OnExtensionMoved(
+    const std::string& moved_extension_id,
+    const std::string& predecessor_extension_id,
+    const std::string& successor_extension_id) {
+  // If there are no neighbors then no changes are required, so we can return.
+  if (predecessor_extension_id.empty() && successor_extension_id.empty())
+    return;
+
+  if (predecessor_extension_id.empty()) {
+    SetAppLaunchOrdinal(
+        moved_extension_id,
+        GetAppLaunchOrdinal(successor_extension_id).CreateBefore());
+  } else if (successor_extension_id.empty()) {
+    SetAppLaunchOrdinal(
+        moved_extension_id,
+        GetAppLaunchOrdinal(predecessor_extension_id).CreateAfter());
+  } else {
+    const StringOrdinal& predecessor_ordinal =
+        GetAppLaunchOrdinal(predecessor_extension_id);
+    const StringOrdinal& successor_ordinal =
+        GetAppLaunchOrdinal(successor_extension_id);
+    SetAppLaunchOrdinal(moved_extension_id,
+                        predecessor_ordinal.CreateBetween(successor_ordinal));
+  }
+
+  content::NotificationService::current()->Notify(
+      chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
+      content::Source<ExtensionPrefs>(this),
+      content::NotificationService::NoDetails());
+}
+
 void ExtensionPrefs::SetExtensionState(const std::string& extension_id,
                                        Extension::State state) {
   UpdateExtensionPref(extension_id, kPrefState,
@@ -1449,79 +1585,180 @@ 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;
+StringOrdinal ExtensionPrefs::GetMinOrMaxAppLaunchOrdinalsOnPage(
+    const StringOrdinal& target_page_ordinal,
+    AppLaunchOrdinalReturn return_type) const {
+  const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
+  CHECK(extensions);
+  CHECK(target_page_ordinal.IsValid());
+
+  StringOrdinal return_value;
+  for (DictionaryValue::key_iterator ext_it = extensions->begin_keys();
+       ext_it != extensions->end_keys(); ++ext_it) {
+    const StringOrdinal& page_ordinal = GetPageOrdinal(*ext_it);
+    if (page_ordinal.IsValid() && page_ordinal.Equal(target_page_ordinal)) {
+      const StringOrdinal& app_launch_ordinal = GetAppLaunchOrdinal(*ext_it);
+      if (app_launch_ordinal.IsValid()) {
+        if (!return_value.IsValid())
+          return_value = app_launch_ordinal;
+        else if (return_type == ExtensionPrefs::MIN_ORDINAL &&
+                 app_launch_ordinal.LessThan(return_value))
+          return_value = app_launch_ordinal;
+        else if (return_type == ExtensionPrefs::MAX_ORDINAL &&
+                 app_launch_ordinal.GreaterThan(return_value))
+          return_value = app_launch_ordinal;
+      }
+    }
+  }
+
+  return return_value;
+}
+
+StringOrdinal ExtensionPrefs::GetAppLaunchOrdinal(
+    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 ordinal
+  // was found.
+  ReadExtensionPrefString(extension_id, kPrefAppLaunchOrdinal, &raw_value);
+  return StringOrdinal(raw_value);
+}
 
-  return -1;
+void ExtensionPrefs::SetAppLaunchOrdinal(const std::string& extension_id,
+                                         const StringOrdinal& ordinal) {
+  UpdateExtensionPref(extension_id, kPrefAppLaunchOrdinal,
+                      Value::CreateStringValue(ordinal.ToString()));
 }
 
-void ExtensionPrefs::SetAppLaunchIndex(const std::string& extension_id,
-                                       int index) {
-  UpdateExtensionPref(extension_id, kPrefAppLaunchIndex,
-                      Value::CreateIntegerValue(index));
+StringOrdinal ExtensionPrefs::CreateFirstAppLaunchOrdinal(
+    const StringOrdinal& page_ordinal) const {
+  const StringOrdinal& min_ordinal =
+      GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
+                                         ExtensionPrefs::MIN_ORDINAL);
+
+  if (min_ordinal.IsValid())
+    return min_ordinal.CreateBefore();
+  else
+    return StringOrdinal::CreateInitialOrdinal();
+}
+
+StringOrdinal ExtensionPrefs::CreateNextAppLaunchOrdinal(
+    const StringOrdinal& page_ordinal) const {
+  const StringOrdinal& max_ordinal =
+      GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
+                                          ExtensionPrefs::MAX_ORDINAL);
+
+  if (max_ordinal.IsValid())
+    return max_ordinal.CreateAfter();
+  else
+    return StringOrdinal::CreateInitialOrdinal();
 }
 
-int ExtensionPrefs::GetNextAppLaunchIndex(int on_page) {
+StringOrdinal ExtensionPrefs::CreateFirstAppPageOrdinal() const {
   const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
-  if (!extensions)
-    return 0;
+  CHECK(extensions);
 
-  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 (page_ordinal_map_.empty())
+    return StringOrdinal::CreateInitialOrdinal();
+
+  return page_ordinal_map_.begin()->first;
 }
 
-int ExtensionPrefs::GetNaturalAppPageIndex() {
+StringOrdinal ExtensionPrefs::GetNaturalAppPageOrdinal() const {
   const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
-  if (!extensions)
-    return 0;
+  CHECK(extensions);
 
-  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_ordinal_map_.empty())
+    return StringOrdinal::CreateInitialOrdinal();
+
+  for (PageOrdinalMap::const_iterator it = page_ordinal_map_.begin();
+       it != page_ordinal_map_.end(); ++it) {
+    if (it->second < kNaturalAppPageSize)
+      return it->first;
   }
+
+  // Add a new page as all existing pages are full.
+  StringOrdinal last_element = page_ordinal_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);
+StringOrdinal ExtensionPrefs::GetPageOrdinal(const std::string& extension_id)
+    const {
+  std::string raw_data;
+  // If the preference read fails then raw_data will still be unset and we will
+  // return an invalid StringOrdinal to signal that no page ordinal was found.
+  ReadExtensionPrefString(extension_id, kPrefPageOrdinal, &raw_data);
+  return StringOrdinal(raw_data);
+}
 
-  content::NotificationService::current()->Notify(
-      chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
-      content::Source<ExtensionPrefs>(this),
-      content::NotificationService::NoDetails());
+void ExtensionPrefs::SetPageOrdinal(const std::string& extension_id,
+                                    const StringOrdinal& page_ordinal) {
+  UpdatePageOrdinalMap(GetPageOrdinal(extension_id), page_ordinal);
+  UpdateExtensionPref(extension_id, kPrefPageOrdinal,
+                      Value::CreateStringValue(page_ordinal.ToString()));
 }
 
-int ExtensionPrefs::GetPageIndex(const std::string& extension_id) {
-  int value = -1;
-  ReadExtensionPrefInteger(extension_id, kPrefPageIndex, &value);
-  return value;
+void ExtensionPrefs::ClearPageOrdinal(const std::string& extension_id) {
+  UpdatePageOrdinalMap(GetPageOrdinal(extension_id), StringOrdinal());
+  UpdateExtensionPref(extension_id, kPrefPageOrdinal, NULL);
+}
+
+void ExtensionPrefs::InitializePageOrdinalMap(
+    const ExtensionIdSet& extension_ids) {
+  for (ExtensionIdSet::const_iterator ext_it = extension_ids.begin();
+       ext_it != extension_ids.end(); ++ext_it) {
+    UpdatePageOrdinalMap(StringOrdinal(), GetPageOrdinal(*ext_it));
+  }
+}
+
+void ExtensionPrefs::UpdatePageOrdinalMap(const StringOrdinal& old_value,
+                                          const StringOrdinal& new_value) {
+  if (new_value.IsValid())
+    ++page_ordinal_map_[new_value];
+
+  if (old_value.IsValid()) {
+    --page_ordinal_map_[old_value];
+
+    if (page_ordinal_map_[old_value] == 0)
+      page_ordinal_map_.erase(old_value);
+  }
 }
 
-void ExtensionPrefs::SetPageIndex(const std::string& extension_id, int index) {
-  UpdateExtensionPref(extension_id, kPrefPageIndex,
-                      Value::CreateIntegerValue(index));
+int ExtensionPrefs::PageStringOrdinalAsInteger(
+    const StringOrdinal& page_ordinal) const {
+  if (!page_ordinal.IsValid())
+    return -1;
+
+  PageOrdinalMap::const_iterator it = page_ordinal_map_.find(page_ordinal);
+  if (it != page_ordinal_map_.end()) {
+    return std::distance(page_ordinal_map_.begin(), it);
+  } else {
+    return -1;
+  }
 }
 
-void ExtensionPrefs::ClearPageIndex(const std::string& extension_id) {
-  UpdateExtensionPref(extension_id, kPrefPageIndex, NULL);
+StringOrdinal ExtensionPrefs::PageIntegerAsStringOrdinal(size_t page_index)
+    const {
+  // We shouldn't have a page_index that is more than 1 position away from the
+  // current end as that would imply we have empty pages which is not allowed.
+  CHECK_LE(page_index, page_ordinal_map_.size());
+
+  const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
+  if (!extensions)
+    return StringOrdinal();
+
+  if (page_index < page_ordinal_map_.size()) {
+    PageOrdinalMap::const_iterator it = page_ordinal_map_.begin();
+    std::advance(it, page_index);
+
+    return it->first;
+
+  } else {
+    if (page_ordinal_map_.empty())
+      return StringOrdinal::CreateInitialOrdinal();
+    else
+      return page_ordinal_map_.rbegin()->first.CreateAfter();
+  }
 }
 
 bool ExtensionPrefs::WasAppDraggedByUser(const std::string& extension_id) {
@@ -1668,7 +1905,9 @@ void ExtensionPrefs::InitPrefStore(bool extensions_disabled) {
   }
 
   FixMissingPrefs(extension_ids);
+  InitializePageOrdinalMap(extension_ids);
   MigratePermissions(extension_ids);
+  MigrateAppIndex(extension_ids);
 
   // Store extension controlled preference values in the
   // |extension_pref_value_map_|, which then informs the subscribers