Separate the NTP app ordering from the app list app ordering

chrome/browser/ui/app_list/app_list_extension_sorting.cc

Index: chrome/browser/ui/app_list/app_list_extension_sorting.cc
diff --git a/chrome/browser/ui/app_list/app_list_extension_sorting.cc b/chrome/browser/ui/app_list/app_list_extension_sorting.cc
new file mode 100644
index 0000000000000000000000000000000000000000..f5cdbf34bb848fc3b0291b011092a86e2a6e90a9
--- /dev/null
+++ b/chrome/browser/ui/app_list/app_list_extension_sorting.cc
@@ -0,0 +1,295 @@
+// Copyright (c) 2013 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/extensions/extension_prefs.h"
+#include "chrome/browser/extensions/extension_service.h"
+#include "chrome/browser/ui/app_list/app_list_extension_sorting.h"
+#include "chrome/common/chrome_notification_types.h"
+#include "content/public/browser/notification_service.h"
+
+#if defined(OS_CHROMEOS)
+#include "chrome/browser/chromeos/extensions/default_app_order.h"
+#endif
+
+namespace {

[xiyuan, 2013/07/05 06:06:18]

nit:

namespace {

const char kPrefAppListOrdinal[] = "app_list_ordinal";

}  // namesapce

[calamity, 2013/07/11 03:31:00]

Done.

+  const char kPrefAppListOrdinal[] = "app_list_ordinal";
+}
+
+AppListExtensionSorting::AppListExtensionSorting(
+    ExtensionScopedPrefs* extension_scoped_prefs)
+    : extension_scoped_prefs_(extension_scoped_prefs),
+      extension_service_(NULL) {}
+
+AppListExtensionSorting::~AppListExtensionSorting() {}
+
+void AppListExtensionSorting::Initialize(
+    const extensions::ExtensionIdList& extension_ids) {
+  std::vector<std::string> uninitialized_extensions;
+  for (extensions::ExtensionIdList::const_iterator ext_it =
+       extension_ids.begin(); ext_it != extension_ids.end(); ++ext_it) {
+    InitializeOrdinalForExtension(*ext_it, uninitialized_extensions);
+    // Ensure that the web store app still isn't found in this list, since
+    // it is added after this loop.
+    DCHECK(*ext_it != extension_misc::kWebStoreAppId);
+    DCHECK(*ext_it != extension_misc::kChromeAppId);
+  }
+
+  // Include the Web Store App since it is displayed on the app list.
+  InitializeOrdinalForExtension(extension_misc::kWebStoreAppId,
+                                uninitialized_extensions);
+  // Include the Chrome App since it is displayed on the app list.
+  InitializeOrdinalForExtension(extension_misc::kChromeAppId,
+                                uninitialized_extensions);
+  InitializeWithDefaultOrdinals(uninitialized_extensions);
+}
+
+void AppListExtensionSorting::InitializeOrdinalForExtension(
+    const std::string extension_id,

[xiyuan, 2013/07/05 06:06:18]

const std::string&

[calamity, 2013/07/11 03:31:00]

Done.

+    std::vector<std::string>& uninitialized_extensions) {

[xiyuan, 2013/07/05 06:06:18]

I don't think we should pass in this. Instead we should make this function
return true/false and update it on the caller side based on the return value.

[calamity, 2013/07/11 03:31:00]

Done.

+  syncer::StringOrdinal ordinal = GetAppListOrdinalFromPrefs(extension_id);
+  if (ordinal.IsValid())
+    SetAppListOrdinal(extension_id, ordinal);
+  else
+    uninitialized_extensions.push_back(extension_id);
+}
+
+void AppListExtensionSorting::InitializeWithDefaultOrdinals(
+    const std::vector<std::string>& uninitialized_extensions) {
+  // The following defines the default order of apps.
+  #if defined(OS_CHROMEOS)

[xiyuan, 2013/07/05 06:06:18]

nit: #if always starts at col 0

[calamity, 2013/07/11 03:31:00]

Done.

+    std::vector<std::string> app_ids;
+    chromeos::default_app_order::Get(&app_ids);
+  #else
+    const char* kDefaultAppOrder[] = {
+      extension_misc::kChromeAppId,
+      extension_misc::kWebStoreAppId,
+    };
+    const std::vector<const char*> app_ids(
+        kDefaultAppOrder, kDefaultAppOrder + arraysize(kDefaultAppOrder));
+  #endif
+
+  syncer::StringOrdinal ordinal = app_list_ordinal_map_.empty()
+      ? syncer::StringOrdinal::CreateInitialOrdinal()
+      : app_list_ordinal_map_.begin()->first.CreateBefore();

[xiyuan, 2013/07/05 06:06:18]

I don't think we should use existing ordinals as a base. The default ordinals
should be a fixed set and not changing from run to run.

[calamity, 2013/07/11 03:31:00]

This is handling when default ordinals are requested when other ordinals already
exist. I think the default ordinals should change to provide sane behavior for
default apps. For example, if we add a new default app in the future, using a
hard-coded ordinal will result in the app being placed in an arbitrary position
in the list. It probably makes more sense to add it at the end rather than the
beginning actually.

[xiyuan, 2013/07/11 05:39:29]

Fixed ordinals do not result in arbitrary position. They would cause conflicts
and would be resolved. Their position should be close to where we intend to put
them (if user has not changed it too much). 

Assuming we have old default apps A,B,C and user apps UA, UB that follows.
- New default app D that is supposed go after C
  Fixed ordinal: D an UA might create a conflict and should give either 
    A,B,C,D,UA,UB or A,B,C,UA,D,UB (depends UA and D's app id)
  New algo would give A,B,C,UA,UB,D
- New default app B1 that is supposed to go between B and C
  Fixed: A,B,B1,C,UA,UB or A,B,C,B1,UA,UB
  New: A,B,C,UA,UB,B1

I personally feel fixed ordinal is closer to my expectation. However, I agree
that fixed ordinal could appear random if user changed the order a lot. And the
new code would always put them in a fixed location, which is good. But neither
front nor end feels right.  I don't know what is the best thing to do here. So
I'll leave it to you to make the call. 

[calamity, 2013/07/15 07:02:32]

After thinking about it, I think front feels more correct. We definitely want
the webstore and chrome apps to appear at the front of the order.

+
+  // Create a map of extension ids to their default ordinals. The first ordinal
+  // used will precede all ordinals in the app list. Subsequent ordinals are
+  // created between this starting ordinal and the first ordinal in the app
+  // list.
+  std::map<std::string, syncer::StringOrdinal> default_ordinals;
+  for (size_t i = 0; i < app_ids.size(); ++i) {
+    const std::string extension_id = app_ids[i];
+    default_ordinals[extension_id] = ordinal;
+    ordinal = app_list_ordinal_map_.empty()
+        ? ordinal.CreateAfter()
+        : ordinal.CreateBetween(app_list_ordinal_map_.begin()->first);
+  }
+
+  // Set default ordinals for uninitialized extensions.
+  for (size_t i = 0; i < uninitialized_extensions.size(); ++i) {
+    std::map<std::string, syncer::StringOrdinal>::const_iterator it =
+        default_ordinals.find(uninitialized_extensions[i]);
+    if (it != default_ordinals.end()) {
+      SetAppListOrdinal(it->first, it->second);

[xiyuan, 2013/07/05 06:06:18]

What if user has changed the default app's position? Wouldn't this reset the
user position?

[calamity, 2013/07/11 03:31:00]

This is only called if the default app is in uninitialized_extensions which is
filled with extensions that don't have ordinals.

+      UpdatePrefs(it->first, it->second);
+      default_initialized_extensions_.push_back(it->first);
+    }
+  }
+}
+
+void AppListExtensionSorting::FixSyncCollisions() {
+  for (AppListOrdinalMap::iterator ordinal_map_it =
+          app_list_ordinal_map_.begin();
+      ordinal_map_it != app_list_ordinal_map_.end(); ++ordinal_map_it) {
+    syncer::StringOrdinal repeated_ordinal = ordinal_map_it->first;
+    ExtensionIdSet& extension_set = ordinal_map_it->second;
+    if (extension_set.size() == 1)
+      continue;
+    // Assign unique ordinals to conflicting extensions by assigning new
+    // ordinals between the conflict ordinal and the next ordinal.
+    AppListOrdinalMap::iterator next_it = ordinal_map_it;
+    std::advance(next_it, 1);
+
+    syncer::StringOrdinal upper_bound_ordinal =
+        next_it == app_list_ordinal_map_.end() ? syncer::StringOrdinal()
+                                               : next_it->first;
+    syncer::StringOrdinal lower_bound_ordinal = repeated_ordinal;
+    std::vector<std::string> conflicting_ids(extension_set.begin(),
+                                             extension_set.end());
+    // Skip the first conflicting extension because the first extension can keep
+    // the conflicted ordinal. Unique ordinals will be assigned so that
+    // conflicts are sorted by their extension ids.
+    for (size_t i = 1; i < conflicting_ids.size(); ++i) {
+      syncer::StringOrdinal unique_ordinal;
+      if (upper_bound_ordinal.IsValid()) {
+        unique_ordinal =
+            lower_bound_ordinal.CreateBetween(upper_bound_ordinal);
+      } else {
+        unique_ordinal = lower_bound_ordinal.CreateAfter();
+      }
+      EraseAppListOrdinal(conflicting_ids[i]);
+      SetAppListOrdinal(conflicting_ids[i], unique_ordinal);
+      UpdatePrefsAndSync(conflicting_ids[i], unique_ordinal);
+      lower_bound_ordinal = unique_ordinal;
+    }
+  }
+
+  content::NotificationService::current()->Notify(
+      chrome::NOTIFICATION_APP_LIST_REORDERED,
+      content::Source<AppListExtensionSorting>(this),
+      content::NotificationService::NoDetails());
+}
+
+void AppListExtensionSorting::InsertAtFront(const std::string& extension_id) {
+  DCHECK(!Contains(extension_id));
+  syncer::StringOrdinal ordinal = app_list_ordinal_map_.empty()
+      ? syncer::StringOrdinal::CreateInitialOrdinal()
+      : app_list_ordinal_map_.begin()->first.CreateBefore();
+  SetAppListOrdinal(extension_id, ordinal);
+  UpdatePrefsAndSync(extension_id, ordinal);
+}
+
+void AppListExtensionSorting::InsertAtBack(const std::string& extension_id) {
+  DCHECK(!Contains(extension_id));
+  syncer::StringOrdinal ordinal = app_list_ordinal_map_.empty()
+      ? syncer::StringOrdinal::CreateInitialOrdinal()
+      : app_list_ordinal_map_.rbegin()->first.CreateAfter();
+  SetAppListOrdinal(extension_id, ordinal);
+  UpdatePrefsAndSync(extension_id, ordinal);
+}
+
+void AppListExtensionSorting::OnExtensionMoved(
+    const std::string& moved_extension_id,
+    const std::string& predecessor_extension_id,
+    const std::string& successor_extension_id) {
+  const syncer::StringOrdinal& predecessor_ordinal =
+      predecessor_extension_id.empty() ?
+          syncer::StringOrdinal() :
+          GetAppListOrdinalFromPrefs(predecessor_extension_id);
+  const syncer::StringOrdinal& successor_ordinal =
+      successor_extension_id.empty() ?
+          syncer::StringOrdinal() :
+          GetAppListOrdinalFromPrefs(successor_extension_id);
+  // We only need to change the StringOrdinal if there is at least one
+  // neighbour.
+  if (predecessor_ordinal.IsValid() || successor_ordinal.IsValid()) {
+    syncer::StringOrdinal ordinal;
+    if (!predecessor_ordinal.IsValid()) {
+      // Only a successor.
+      ordinal = successor_ordinal.CreateBefore();
+    } else if (!successor_ordinal.IsValid()) {
+      // Only a predecessor.
+      ordinal = predecessor_ordinal.CreateAfter();
+    } else {
+      // Both a successor and predecessor
+      ordinal = predecessor_ordinal.CreateBetween(successor_ordinal);
+    }
+    EraseAppListOrdinal(moved_extension_id);
+    SetAppListOrdinal(moved_extension_id, ordinal);
+    UpdatePrefsAndSync(moved_extension_id, ordinal);
+  }
+
+  content::NotificationService::current()->Notify(
+      chrome::NOTIFICATION_APP_LIST_REORDERED,
+      content::Source<AppListExtensionSorting>(this),
+      content::Details<const std::string>(&moved_extension_id));
+}
+
+void AppListExtensionSorting::Erase(const std::string& extension_id) {
+  EraseAppListOrdinal(extension_id);
+  UpdatePrefsAndSync(extension_id, syncer::StringOrdinal());
+}
+
+void AppListExtensionSorting::EraseAppListOrdinal(
+    const std::string& extension_id) {
+  if (!Contains(extension_id))
+    return;
+  AppListOrdinalMap::iterator ordinal_map_it =
+      app_list_ordinal_map_.find(GetAppListOrdinalFromPrefs(extension_id));
+  if (ordinal_map_it == app_list_ordinal_map_.end())
+    NOTREACHED();
+  ordinal_map_it->second.erase(extension_id);
+  if (ordinal_map_it->second.empty())
+    app_list_ordinal_map_.erase(ordinal_map_it);
+}
+
+bool AppListExtensionSorting::ExtensionPrecedes(
+    const std::string& extension_id1,
+    const std::string& extension_id2) {
+  if (!Contains(extension_id1))

[xiyuan, 2013/07/05 06:06:18]

Would the unknown ID case ever going to happen? If not, we should CHECK or
DCHECK the unknown id case. 

[calamity, 2013/07/11 03:31:00]

Done. This now DCHECKs but maintains reasonable failure behavior.

[xiyuan, 2013/07/11 05:39:29]

We don't need both. If the failure is not supposed to happen, we should CHECK or
DCHECK. Otherwise, we should keep the "if" and not CHECK.

[calamity, 2013/07/15 07:02:32]

Done.

+    return false;
+  if (!Contains(extension_id2))
+    return true;
+  return GetAppListOrdinalFromPrefs(extension_id1).LessThan(
+      GetAppListOrdinalFromPrefs(extension_id2));
+}
+
+bool AppListExtensionSorting::Contains(const std::string& extension) {
+  return GetAppListOrdinalFromPrefs(extension).IsValid();
+}
+
+syncer::StringOrdinal AppListExtensionSorting::GetAppListOrdinalFromPrefs(
+    const std::string& extension_id) {
+  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 app list ordinal was
+  // found.
+  extension_scoped_prefs_->ReadPrefAsString(
+      extension_id, kPrefAppListOrdinal, &raw_data);
+  return syncer::StringOrdinal(raw_data);
+}
+
+void AppListExtensionSorting::UpdateAppListOrdinalFromSync(
+  const std::string& extension_id,
+  const syncer::StringOrdinal& ordinal) {
+  EraseAppListOrdinal(extension_id);
+  SetAppListOrdinal(extension_id, ordinal);
+  UpdatePrefsAndSync(extension_id, ordinal);
+}
+
+void AppListExtensionSorting::SetAppListOrdinal(
+    const std::string& extension_id,
+    const syncer::StringOrdinal& ordinal) {
+  app_list_ordinal_map_[ordinal].insert(extension_id);
+}
+
+void AppListExtensionSorting::UpdatePrefs(
+    const std::string& extension_id,
+    const syncer::StringOrdinal& ordinal) {
+  if (ordinal.EqualsOrBothInvalid(GetAppListOrdinalFromPrefs(extension_id)))
+    return;
+  Value* new_value = ordinal.IsValid() ?
+      Value::CreateStringValue(ordinal.ToInternalValue()) :
+      NULL;
+  extension_scoped_prefs_->UpdateExtensionPref(
+      extension_id,
+      kPrefAppListOrdinal,
+      new_value);
+}
+
+void AppListExtensionSorting::UpdatePrefsAndSync(
+    const std::string& extension_id,
+    const syncer::StringOrdinal& ordinal) {
+  UpdatePrefs(extension_id, ordinal);
+  // Sync extension pref.
+  if (!extension_service_)
+    NOTREACHED();
+  const extensions::Extension* extension =
+      extension_service_->GetInstalledExtension(extension_id);
+  if (extension)
+    extension_service_->SyncExtensionChangeIfNeeded(*extension);
+}
+
+void AppListExtensionSorting::SetExtensionService(
+    ExtensionServiceInterface* extension_service) {
+  extension_service_ = extension_service;
+  for (size_t i = 0; i < default_initialized_extensions_.size(); ++i) {
+    const extensions::Extension* extension =
+      extension_service_->GetInstalledExtension(
+          default_initialized_extensions_[i]);
+    if (extension)
+      extension_service_->SyncExtensionChangeIfNeeded(*extension);
+  }
+  default_initialized_extensions_.clear();
+}