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 ebe337cc0b60403f3c82af43d9fae8d2f6495a9b..11e9414fa15a02206e15bb3ccdbb0b0c213ed1b7 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 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";
@@ -415,6 +417,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 +871,87 @@ 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

[akalin, 2011/12/01 02:57:47]

can't you do a two-level map, the outer one keyed by page ordinal and the inner
one keyed by page index values?  That seems clearer than lumping all the app
indices together

[csharp, 2011/12/01 20:15:09]

Done.

+  // app launch values that need to be migrated, inserted them into a sorted
+  // set to be dealt with later.
+  std::multimap<int,const std::string*> app_launches_to_convert;

[akalin, 2011/12/01 02:57:47]

space after 'int,'

[csharp, 2011/12/01 20:15:09]

Done.

+  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)) {
+      // Since we require all earlier StringOrdinals to already exist in order
+      // to properly convert from integers and we are iteratoring 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_.size() == 0)

[akalin, 2011/12/01 02:57:47]

.empty()

[csharp, 2011/12/01 20:15:09]

Done.

+        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.insert(
+            std::pair<int,const std::string*>(

[akalin, 2011/12/01 02:57:47]

use std::make_pair

[csharp, 2011/12/01 20:15:09]

Done.

+                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 (std::map<StringOrdinal, int, StringOrdinalLessThan>::iterator it =
+      page_ordinal_map_.begin(); it != page_ordinal_map_.end();) {
+    if (it->second == 0) {
+      std::map<StringOrdinal, int, StringOrdinalLessThan>::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 (std::multimap<int, const std::string*>
+           ::const_iterator ext = app_launches_to_convert.begin();
+       ext != app_launches_to_convert.end(); ++ext) {
+    StringOrdinal page = GetPageOrdinal(*(ext->second));
+    SetAppLaunchOrdinal(*(ext->second),
+                        CreateNextAppLaunchOrdinal(page));
+  }
+}
+
 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) {
+    const StringOrdinal& page_ordinal) {
   const std::string& id = extension->id();
   CHECK(Extension::IdIsValid(id));
   ScopedExtensionPrefUpdate update(prefs_, id);
@@ -1104,13 +1198,17 @@ 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)));
+    if (page_ordinal.IsValid()) {
+      SetPageOrdinal(id, page_ordinal);
+      SetAppLaunchOrdinal(id, CreateNextAppLaunchOrdinal(page_ordinal));
+

[akalin, 2011/12/01 02:57:47]

remove extra space

[csharp, 2011/12/01 20:15:09]

Done.

+    } else {
+      StringOrdinal new_page_ordinal = GetNaturalAppPageOrdinal();

[akalin, 2011/12/01 02:57:47]

by 'inline this code' i meant inline and eliminate redundancy.  The two clauses
differ only in the page ordinal.

[csharp, 2011/12/01 20:15:09]

Ok, I think I've fixed this but I'm not 100% sure what you mean. I now replace
page_ordinal if it is invalid, but that means it is no longer passed in as a
const reference since it can change. Is this what you meant?


On 2011/12/01 02:57:47, akalin wrote:

[akalin, 2011/12/01 20:42:46]

I meant something like:

StringOrdinal new_page_ordinal = page_ordinal.IsValid() ? page_ordinal :
GetNatural...;
SetPageOrdinal(...);
SetAppLaunchOrdinal(...);

+      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(
@@ -1135,6 +1233,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 {
+    StringOrdinal predecessor_ordinal =

[akalin, 2011/12/01 02:57:47]

const ref

[csharp, 2011/12/01 20:15:09]

Done.

+        GetAppLaunchOrdinal(predecessor_extension_id);
+    StringOrdinal successor_ordinal =

[akalin, 2011/12/01 02:57:47]

const ref

[csharp, 2011/12/01 20:15:09]

Done.

+        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,
@@ -1442,79 +1571,181 @@ 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::GetMinAndMaxAppLaunchOrdinalsOnPage(
+    const StringOrdinal& target_page_ordinal,
+    StringOrdinal* min_app_launch_value,
+    StringOrdinal* max_app_launch_value) const {
+  const DictionaryValue* extensions = prefs_->GetDictionary(kExtensionsPref);
+  CHECK(extensions);
+  CHECK(target_page_ordinal.IsValid());
+  CHECK(min_app_launch_value);
+  CHECK(max_app_launch_value);
+
+  for (DictionaryValue::key_iterator ext_it = extensions->begin_keys();
+       ext_it != extensions->end_keys(); ++ext_it) {
+    StringOrdinal page_ordinal = GetPageOrdinal(*ext_it);
+    if (page_ordinal.IsValid() && page_ordinal.Equal(target_page_ordinal)) {
+      StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(*ext_it);

[akalin, 2011/12/01 02:57:47]

const ref

[csharp, 2011/12/01 20:15:09]

Done.

+      if (app_launch_ordinal.IsValid()) {
+        if (!min_app_launch_value->IsValid() ||
+            app_launch_ordinal.LessThan(*min_app_launch_value))
+          *min_app_launch_value = app_launch_ordinal;
+
+        if (!max_app_launch_value->IsValid() ||
+            max_app_launch_value->LessThan(app_launch_ordinal))

[akalin, 2011/12/01 02:57:47]

surely you mean GreaterThan?  Why didn't any tests catch this?  Do you need to
write one for this function?

[csharp, 2011/12/01 20:15:09]

This was the correct call, the operators are in the different order than the one
above. 

To prevent this confusion though I'd changed it to call GreaterThan, I also
added a test for this function.

On 2011/12/01 02:57:47, akalin wrote:

+          *max_app_launch_value = app_launch_ordinal;
+      }
+    }
+  }
+}
+
+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);
+}
+
+void ExtensionPrefs::SetAppLaunchOrdinal(const std::string& extension_id,
+                                         const StringOrdinal& ordinal) {
+  UpdateExtensionPref(extension_id, kPrefAppLaunchOrdinal,
+                      Value::CreateStringValue(ordinal.ToString()));
+}
+
+StringOrdinal ExtensionPrefs::CreateFirstAppLaunchOrdinal(
+    const StringOrdinal& page_ordinal) const {
+  StringOrdinal max_ordinal;
+  StringOrdinal min_ordinal;
+  GetMinAndMaxAppLaunchOrdinalsOnPage(page_ordinal, &min_ordinal, &max_ordinal);
 
-  return -1;
+  if (min_ordinal.IsValid())
+    return min_ordinal.CreateBefore();
+  else
+    return StringOrdinal::CreateInitialOrdinal();
 }
 
-void ExtensionPrefs::SetAppLaunchIndex(const std::string& extension_id,
-                                       int index) {
-  UpdateExtensionPref(extension_id, kPrefAppLaunchIndex,
-                      Value::CreateIntegerValue(index));
+StringOrdinal ExtensionPrefs::CreateNextAppLaunchOrdinal(
+    const StringOrdinal& page_ordinal) const {
+  StringOrdinal max_ordinal;
+  StringOrdinal min_ordinal;
+  GetMinAndMaxAppLaunchOrdinalsOnPage(page_ordinal, &min_ordinal, &max_ordinal);
+
+  if (max_ordinal.IsValid())
+    return max_ordinal.CreateAfter();
+  else
+    return StringOrdinal::CreateInitialOrdinal();
 }
 
-int ExtensionPrefs::GetNextAppLaunchIndex(int on_page) {
+StringOrdinal ExtensionPrefs::CreateFirstAppPage() 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 (std::map<StringOrdinal, int>::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;
+
+  std::map<StringOrdinal, int>::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()) {
+    std::map<StringOrdinal, int, StringOrdinalLessThan>::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) {
@@ -1661,7 +1892,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