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..6367a2bb911bd1b6141d5e6912f06479114b25a4 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";
@@ -239,6 +241,28 @@ std::string JoinPrefs(std::string parent, const char* child) {
   return parent + "." + child;
 }
 
+// A simple structure used when sorting applications based on their app launch
+// index. This is used by the code that migrates the data from integers to
+// StringOrdinals.
+struct ApplicationNTPOldAppLaunch {
+  const std::string* application_id;
+  const int app_launch_index;
+
+  ApplicationNTPOldAppLaunch() : application_id(0),
+                                 app_launch_index(0) {}
+
+  ApplicationNTPOldAppLaunch(const std::string& app_id, int app_launch)
+      : application_id(&app_id),
+        app_launch_index(app_launch) {}
+};
+
+struct SortByNTPOldAppLaunch {
+  bool operator() (const ApplicationNTPOldAppLaunch& lhs,
+                   const ApplicationNTPOldAppLaunch& rhs) const {
+    return lhs.app_launch_index < rhs.app_launch_index;
+  }
+};
+
 }  // namespace
 
 ExtensionPrefs::ExtensionPrefs(
@@ -415,6 +439,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 +893,65 @@ 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.
+  std::multiset<ApplicationNTPOldAppLaunch, SortByNTPOldAppLaunch>
+      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;
+    if (ReadExtensionPrefInteger(*ext_id,
+                                 kPrefPageIndexDeprecated,
+                                 &old_page_index)) {
+      SetPageOrdinal(*ext_id, PageIntegerAsStringOrdinal(old_page_index));
+      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.
+      app_launches_to_convert.insert(ApplicationNTPOldAppLaunch(
+          *ext_id,
+          old_app_launch_index));
+  }
+
+  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::multiset<ApplicationNTPOldAppLaunch, SortByNTPOldAppLaunch>
+           ::const_iterator ext = app_launches_to_convert.begin();
+       ext != app_launches_to_convert.end(); ++ext) {
+    int old_app_launch_index;
+    if (ReadExtensionPrefInteger(*(ext->application_id),

[akalin, 2011/11/23 18:50:19]

why is this conditional still needed?  you already did it in the first loop,
right?  you're not even using the value

[csharp, 2011/11/23 22:10:01]

Done.

+                                 kPrefAppLaunchIndexDeprecated,
+                                 &old_app_launch_index)) {
+      StringOrdinal page = GetPageOrdinal(*(ext->application_id));
+      if (!page.IsValid()) {

[akalin, 2011/11/23 18:50:19]

can you fold this into the first loop?  it can be an 'else' statement to the
first if statement of the first loop, right?

[csharp, 2011/11/23 22:10:01]

I thought it could, but unit tests proved me wrong.
If we do it as an else to the first if statement we end up creating ordinal
value for extensions that shouldn't have it, since we don't (at this point) have
a good way of knowing what should have values and what shouldn't.

The only reason we aren't bitten by this problem in the other loop is because we
at least found a app launch value that needed to be migrated, we know a page
ordinal is required.


On 2011/11/23 18:50:19, akalin wrote:

[akalin, 2011/11/29 18:39:09]

Ah, I see.  But it can certainly still be in the first loop.  Something like:

for (...) {
  StringOrdinal page;
  if (ReadExtensionPref...kPrefPageIndex...) {
    page = PageIntegerAsStringOrdinal(old_page_index);
    ...
  }

  if (ReadExtensionPref...kPrefAppLaunchIndexDeprecated) {
    ...
    if (!page.isValid()) {
      ...
    }
  }
}

Basically, the second loop exists only because we have to set the app launch
indices in a certain order.  So that should be all it's doing.

[csharp, 2011/11/29 21:21:40]

Done.

+        page = GetNaturalAppPageOrdinal();
+        SetPageOrdinal(*(ext->application_id), page);
+      }
+
+      SetAppLaunchOrdinal(*(ext->application_id),
+                          GetNextAppLaunchOrdinal(page));
+      UpdateExtensionPref(

[akalin, 2011/11/23 18:50:19]

can you do this in the first loop?

[csharp, 2011/11/23 22:10:01]

Done.

+          *(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_ordinal) {

[akalin, 2011/11/23 18:50:19]

const ref

[csharp, 2011/11/23 22:10:01]

Done.

   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)
-      page_index = GetNaturalAppPageIndex();
-    extension_dict->Set(kPrefPageIndex,
-                        Value::CreateIntegerValue(page_index));
-    extension_dict->Set(kPrefAppLaunchIndex,
-        Value::CreateIntegerValue(GetNextAppLaunchIndex(page_index)));
+    if (!page_ordinal.IsValid())
+      page_ordinal = GetNaturalAppPageOrdinal();
+    extension_dict->Set(kPrefPageOrdinal,
+                        Value::CreateStringValue(page_ordinal.ToString()));
+    UpdatePageOrdinalMap(StringOrdinal(), page_ordinal);
+
+    extension_dict->Set(kPrefAppLaunchOrdinal,
+                        Value::CreateStringValue(
+                            GetNextAppLaunchOrdinal(page_ordinal).ToString()));
   }
   extension_pref_value_map_->RegisterExtension(
       id, install_time, initial_state == Extension::ENABLED);
@@ -1442,59 +1539,147 @@ 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;
+bool ExtensionPrefs::GetMaxAndMinAppLaunchOrdinalsOnPage(
+    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);
+
+  StringOrdinal* min_value = NULL;
+  StringOrdinal* max_value = NULL;
+  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);
+      if (app_launch_ordinal.IsValid()) {
+        if (min_value == NULL || !min_value->IsValid() ||
+            app_launch_ordinal.LessThan(*min_value))
+          min_value = &app_launch_ordinal;
+
+        if (max_value == NULL || !max_value->IsValid() ||
+            max_value->LessThan(app_launch_ordinal))
+          max_value = &app_launch_ordinal;
+      }
+    }
+  }
 
-  return -1;
-}
+  if (min_value != NULL)
+    *min_app_launch_value = *min_value;
+  if (max_value != NULL)
+    *max_app_launch_value = *max_value;
 
-void ExtensionPrefs::SetAppLaunchIndex(const std::string& extension_id,
-                                       int index) {
-  UpdateExtensionPref(extension_id, kPrefAppLaunchIndex,
-                      Value::CreateIntegerValue(index));
+  // If |min_app_launch_value| is valid then we had at least 1 app on the page,
+  // so both positions are valid.
+  return min_app_launch_value->IsValid();
 }
 
-int ExtensionPrefs::GetNextAppLaunchIndex(int on_page) {
+StringOrdinal ExtensionPrefs::GetFirstAppPage() 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;
+}
+
+StringOrdinal ExtensionPrefs::CreateFirstAppLaunchOrdinal(
+    const StringOrdinal& page_ordinal) const {
+  StringOrdinal max_ordinal;
+  StringOrdinal min_ordinal;
+  GetMaxAndMinAppLaunchOrdinalsOnPage(page_ordinal, &min_ordinal, &max_ordinal);
+
+  if (min_ordinal.IsValid())
+    return min_ordinal.CreateBefore();
+  else
+    return StringOrdinal::CreateInitialOrdinal();
+}
+
+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::GetNextAppLaunchOrdinal(
+    const StringOrdinal& page_ordinal) const {
+  StringOrdinal max_ordinal;
+  StringOrdinal min_ordinal;
+  GetMaxAndMinAppLaunchOrdinalsOnPage(page_ordinal, &min_ordinal, &max_ordinal);
+
+  if (max_ordinal.IsValid())
+    return max_ordinal.CreateAfter();
+  else
+    return StringOrdinal::CreateInitialOrdinal();
 }
 
-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();
+
+  std::map<StringOrdinal, int>::const_iterator it = page_ordinal_map_.begin();
+  for (; 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);
+    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);
+  CHECK(it != extension_ids.end());
+  size_t position = it - extension_ids.begin();
+
+  // 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;
+      SetAppLaunchOrdinal(moved_extension_id,
+                          GetAppLaunchOrdinal(*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;
+      SetAppLaunchOrdinal(moved_extension_id,
+                          GetAppLaunchOrdinal(*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 = GetAppLaunchOrdinal(*it);
+      it -= 2;
+      StringOrdinal value_before = GetAppLaunchOrdinal(*it);
+      SetAppLaunchOrdinal(moved_extension_id,
+                          value_before.CreateBetween(value_after));
+    }
+  }
 
   content::NotificationService::current()->Notify(
       chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
@@ -1502,19 +1687,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::GetPageOrdinal(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

[akalin, 2011/11/23 18:50:19]

raw_value -> raw_data

[csharp, 2011/11/23 22:10:01]

Done.

+  // return an invalid StringOrdinal to signal that no page ordinal was found.
+  ReadExtensionPrefString(extension_id, kPrefPageOrdinal, &raw_data);
+  return StringOrdinal(raw_data);
+}
+
+void ExtensionPrefs::SetPageOrdinal(const std::string& extension_id,
+                                  const StringOrdinal& page_ordinal) {

[akalin, 2011/11/23 18:50:19]

indent

[csharp, 2011/11/23 22:10:01]

Done.

+  UpdatePageOrdinalMap(GetPageOrdinal(extension_id), page_ordinal);
+  UpdateExtensionPref(extension_id, kPrefPageOrdinal,
+                      Value::CreateStringValue(page_ordinal.ToString()));
 }
 
-void ExtensionPrefs::SetPageIndex(const std::string& extension_id, int index) {
-  UpdateExtensionPref(extension_id, kPrefPageIndex,
-                      Value::CreateIntegerValue(index));
+void ExtensionPrefs::ClearPageOrdinal(const std::string& extension_id) {
+  UpdatePageOrdinalMap(GetPageOrdinal(extension_id), StringOrdinal());
+  UpdateExtensionPref(extension_id, kPrefPageOrdinal, NULL);
 }
 
-void ExtensionPrefs::ClearPageIndex(const std::string& extension_id) {
-  UpdateExtensionPref(extension_id, kPrefPageIndex, 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);
+  }
+}
+
+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;
+  }
+}
+
+StringOrdinal ExtensionPrefs::PageIntegerAsStringOrdinal(size_t page_index) {
+  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();
+    advance(it, page_index);
+
+    return it->first;
+  } else {
+    if (page_ordinal_map_.empty())
+      page_ordinal_map_[StringOrdinal::CreateInitialOrdinal()] = 0;
+
+    // Create new pages until we reach the desired index.
+    while (page_index >= page_ordinal_map_.size()) {
+      StringOrdinal new_page = page_ordinal_map_.rbegin()->first.CreateAfter();
+      page_ordinal_map_[new_page] = 0;
+    }
+    return page_ordinal_map_.rbegin()->first;
+  }
 }
 
 bool ExtensionPrefs::WasAppDraggedByUser(const std::string& extension_id) {
@@ -1661,7 +1912,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