1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #include "chrome/browser/extensions/chrome_app_sorting.h"
10 #include "chrome/browser/chrome_notification_types.h"
11 #include "chrome/browser/extensions/extension_sync_service.h"
12 #include "chrome/common/extensions/extension_constants.h"
13 #include "content/public/browser/notification_service.h"
14 #include "extensions/browser/extension_scoped_prefs.h"
15 #include "extensions/common/extension.h"
17 #if defined(OS_CHROMEOS)
18 #include "chrome/browser/chromeos/extensions/default_app_order.h"
21 namespace extensions {
25 // The number of apps per page. This isn't a hard limit, but new apps installed
26 // from the webstore will overflow onto a new page if this limit is reached.
27 const size_t kNaturalAppPageSize = 18;
29 // A preference determining the order of which the apps appear on the NTP.
30 const char kPrefAppLaunchIndexDeprecated[] = "app_launcher_index";
31 const char kPrefAppLaunchOrdinal[] = "app_launcher_ordinal";
33 // A preference determining the page on which an app appears in the NTP.
34 const char kPrefPageIndexDeprecated[] = "page_index";
35 const char kPrefPageOrdinal[] = "page_ordinal";
39 ////////////////////////////////////////////////////////////////////////////////
40 // ChromeAppSorting::AppOrdinals
42 ChromeAppSorting::AppOrdinals::AppOrdinals() {}
44 ChromeAppSorting::AppOrdinals::~AppOrdinals() {}
46 ////////////////////////////////////////////////////////////////////////////////
49 ChromeAppSorting::ChromeAppSorting()
50 : extension_scoped_prefs_(NULL),
51 extension_sync_service_(NULL),
52 default_ordinals_created_(false) {
55 ChromeAppSorting::~ChromeAppSorting() {
58 void ChromeAppSorting::SetExtensionScopedPrefs(ExtensionScopedPrefs* prefs) {
59 extension_scoped_prefs_ = prefs;
62 void ChromeAppSorting::SetExtensionSyncService(
63 ExtensionSyncService* extension_sync_service) {
64 extension_sync_service_ = extension_sync_service;
67 void ChromeAppSorting::Initialize(
68 const extensions::ExtensionIdList& extension_ids) {
69 InitializePageOrdinalMap(extension_ids);
71 MigrateAppIndex(extension_ids);
74 void ChromeAppSorting::CreateOrdinalsIfNecessary(size_t minimum_size) {
75 // Create StringOrdinal values as required to ensure |ntp_ordinal_map_| has at
76 // least |minimum_size| entries.
77 if (ntp_ordinal_map_.empty() && minimum_size > 0)
78 ntp_ordinal_map_[syncer::StringOrdinal::CreateInitialOrdinal()];
80 while (ntp_ordinal_map_.size() < minimum_size) {
81 syncer::StringOrdinal filler =
82 ntp_ordinal_map_.rbegin()->first.CreateAfter();
83 AppLaunchOrdinalMap empty_ordinal_map;
84 ntp_ordinal_map_.insert(std::make_pair(filler, empty_ordinal_map));
88 void ChromeAppSorting::MigrateAppIndex(
89 const extensions::ExtensionIdList& extension_ids) {
90 if (extension_ids.empty())
93 // Convert all the page index values to page ordinals. If there are any
94 // app launch values that need to be migrated, inserted them into a sorted
95 // set to be dealt with later.
96 typedef std::map<syncer::StringOrdinal, std::map<int, const std::string*>,
97 syncer::StringOrdinal::LessThanFn> AppPositionToIdMapping;
98 AppPositionToIdMapping app_launches_to_convert;
99 for (extensions::ExtensionIdList::const_iterator ext_id =
100 extension_ids.begin(); ext_id != extension_ids.end(); ++ext_id) {
101 int old_page_index = 0;
102 syncer::StringOrdinal page = GetPageOrdinal(*ext_id);
103 if (extension_scoped_prefs_->ReadPrefAsInteger(
105 kPrefPageIndexDeprecated,
107 // Some extensions have invalid page index, so we don't
108 // attempt to convert them.
109 if (old_page_index < 0) {
110 DLOG(WARNING) << "Extension " << *ext_id
111 << " has an invalid page index " << old_page_index
112 << ". Aborting attempt to convert its index.";
116 CreateOrdinalsIfNecessary(static_cast<size_t>(old_page_index) + 1);
118 page = PageIntegerAsStringOrdinal(old_page_index);
119 SetPageOrdinal(*ext_id, page);
120 extension_scoped_prefs_->UpdateExtensionPref(
121 *ext_id, kPrefPageIndexDeprecated, NULL);
124 int old_app_launch_index = 0;
125 if (extension_scoped_prefs_->ReadPrefAsInteger(
127 kPrefAppLaunchIndexDeprecated,
128 &old_app_launch_index)) {
129 // We can't update the app launch index value yet, because we use
130 // GetNextAppLaunchOrdinal to get the new ordinal value and it requires
131 // all the ordinals with lower values to have already been migrated.
132 // A valid page ordinal is also required because otherwise there is
133 // no page to add the app to.
135 app_launches_to_convert[page][old_app_launch_index] = &*ext_id;
137 extension_scoped_prefs_->UpdateExtensionPref(
138 *ext_id, kPrefAppLaunchIndexDeprecated, NULL);
142 // Remove any empty pages that may have been added. This shouldn't occur,
143 // but double check here to prevent future problems with conversions between
144 // integers and StringOrdinals.
145 for (PageOrdinalMap::iterator it = ntp_ordinal_map_.begin();
146 it != ntp_ordinal_map_.end();) {
147 if (it->second.empty()) {
148 PageOrdinalMap::iterator prev_it = it;
150 ntp_ordinal_map_.erase(prev_it);
156 if (app_launches_to_convert.empty())
159 // Create the new app launch ordinals and remove the old preferences. Since
160 // the set is sorted, each time we migrate an apps index, we know that all of
161 // the remaining apps will appear further down the NTP than it or on a
163 for (AppPositionToIdMapping::const_iterator page_it =
164 app_launches_to_convert.begin();
165 page_it != app_launches_to_convert.end(); ++page_it) {
166 syncer::StringOrdinal page = page_it->first;
167 for (std::map<int, const std::string*>::const_iterator launch_it =
168 page_it->second.begin(); launch_it != page_it->second.end();
170 SetAppLaunchOrdinal(*(launch_it->second),
171 CreateNextAppLaunchOrdinal(page));
176 void ChromeAppSorting::FixNTPOrdinalCollisions() {
177 for (PageOrdinalMap::iterator page_it = ntp_ordinal_map_.begin();
178 page_it != ntp_ordinal_map_.end(); ++page_it) {
179 AppLaunchOrdinalMap& page = page_it->second;
181 AppLaunchOrdinalMap::iterator app_launch_it = page.begin();
182 while (app_launch_it != page.end()) {
183 int app_count = page.count(app_launch_it->first);
184 if (app_count == 1) {
189 syncer::StringOrdinal repeated_ordinal = app_launch_it->first;
191 // Sort the conflicting keys by their extension id, this is how
192 // the order is decided.
193 std::vector<std::string> conflicting_ids;
194 for (int i = 0; i < app_count; ++i, ++app_launch_it)
195 conflicting_ids.push_back(app_launch_it->second);
196 std::sort(conflicting_ids.begin(), conflicting_ids.end());
198 syncer::StringOrdinal upper_bound_ordinal = app_launch_it == page.end() ?
199 syncer::StringOrdinal() :
200 app_launch_it->first;
201 syncer::StringOrdinal lower_bound_ordinal = repeated_ordinal;
203 // Start at position 1 because the first extension can keep the conflicted
205 for (int i = 1; i < app_count; ++i) {
206 syncer::StringOrdinal unique_app_launch;
207 if (upper_bound_ordinal.IsValid()) {
209 lower_bound_ordinal.CreateBetween(upper_bound_ordinal);
211 unique_app_launch = lower_bound_ordinal.CreateAfter();
214 SetAppLaunchOrdinal(conflicting_ids[i], unique_app_launch);
215 lower_bound_ordinal = unique_app_launch;
220 content::NotificationService::current()->Notify(
221 chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
222 content::Source<ChromeAppSorting>(this),
223 content::NotificationService::NoDetails());
226 void ChromeAppSorting::EnsureValidOrdinals(
227 const std::string& extension_id,
228 const syncer::StringOrdinal& suggested_page) {
229 syncer::StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
230 if (!page_ordinal.IsValid()) {
231 if (suggested_page.IsValid()) {
232 page_ordinal = suggested_page;
233 } else if (!GetDefaultOrdinals(extension_id, &page_ordinal, NULL) ||
234 !page_ordinal.IsValid()) {
235 page_ordinal = GetNaturalAppPageOrdinal();
238 SetPageOrdinal(extension_id, page_ordinal);
241 syncer::StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
242 if (!app_launch_ordinal.IsValid()) {
243 // If using default app launcher ordinal, make sure there is no collision.
244 if (GetDefaultOrdinals(extension_id, NULL, &app_launch_ordinal) &&
245 app_launch_ordinal.IsValid())
246 app_launch_ordinal = ResolveCollision(page_ordinal, app_launch_ordinal);
248 app_launch_ordinal = CreateNextAppLaunchOrdinal(page_ordinal);
250 SetAppLaunchOrdinal(extension_id, app_launch_ordinal);
254 void ChromeAppSorting::OnExtensionMoved(
255 const std::string& moved_extension_id,
256 const std::string& predecessor_extension_id,
257 const std::string& successor_extension_id) {
258 // We only need to change the StringOrdinal if there are neighbours.
259 if (!predecessor_extension_id.empty() || !successor_extension_id.empty()) {
260 if (predecessor_extension_id.empty()) {
264 GetAppLaunchOrdinal(successor_extension_id).CreateBefore());
265 } else if (successor_extension_id.empty()) {
266 // Only a predecessor.
269 GetAppLaunchOrdinal(predecessor_extension_id).CreateAfter());
271 // Both a successor and predecessor
272 const syncer::StringOrdinal& predecessor_ordinal =
273 GetAppLaunchOrdinal(predecessor_extension_id);
274 const syncer::StringOrdinal& successor_ordinal =
275 GetAppLaunchOrdinal(successor_extension_id);
276 SetAppLaunchOrdinal(moved_extension_id,
277 predecessor_ordinal.CreateBetween(successor_ordinal));
281 SyncIfNeeded(moved_extension_id);
283 content::NotificationService::current()->Notify(
284 chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
285 content::Source<ChromeAppSorting>(this),
286 content::Details<const std::string>(&moved_extension_id));
290 syncer::StringOrdinal ChromeAppSorting::GetAppLaunchOrdinal(
291 const std::string& extension_id) const {
292 std::string raw_value;
293 // If the preference read fails then raw_value will still be unset and we
294 // will return an invalid StringOrdinal to signal that no app launch ordinal
296 extension_scoped_prefs_->ReadPrefAsString(
297 extension_id, kPrefAppLaunchOrdinal, &raw_value);
298 return syncer::StringOrdinal(raw_value);
301 void ChromeAppSorting::SetAppLaunchOrdinal(
302 const std::string& extension_id,
303 const syncer::StringOrdinal& new_app_launch_ordinal) {
304 // No work is required if the old and new values are the same.
305 if (new_app_launch_ordinal.EqualsOrBothInvalid(
306 GetAppLaunchOrdinal(extension_id))) {
310 syncer::StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
311 RemoveOrdinalMapping(
312 extension_id, page_ordinal, GetAppLaunchOrdinal(extension_id));
313 AddOrdinalMapping(extension_id, page_ordinal, new_app_launch_ordinal);
315 base::Value* new_value = new_app_launch_ordinal.IsValid() ?
316 new base::StringValue(new_app_launch_ordinal.ToInternalValue()) :
319 extension_scoped_prefs_->UpdateExtensionPref(
321 kPrefAppLaunchOrdinal,
323 SyncIfNeeded(extension_id);
326 syncer::StringOrdinal ChromeAppSorting::CreateFirstAppLaunchOrdinal(
327 const syncer::StringOrdinal& page_ordinal) const {
328 const syncer::StringOrdinal& min_ordinal =
329 GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
330 ChromeAppSorting::MIN_ORDINAL);
332 if (min_ordinal.IsValid())
333 return min_ordinal.CreateBefore();
335 return syncer::StringOrdinal::CreateInitialOrdinal();
338 syncer::StringOrdinal ChromeAppSorting::CreateNextAppLaunchOrdinal(
339 const syncer::StringOrdinal& page_ordinal) const {
340 const syncer::StringOrdinal& max_ordinal =
341 GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
342 ChromeAppSorting::MAX_ORDINAL);
344 if (max_ordinal.IsValid())
345 return max_ordinal.CreateAfter();
347 return syncer::StringOrdinal::CreateInitialOrdinal();
350 syncer::StringOrdinal ChromeAppSorting::CreateFirstAppPageOrdinal() const {
351 if (ntp_ordinal_map_.empty())
352 return syncer::StringOrdinal::CreateInitialOrdinal();
354 return ntp_ordinal_map_.begin()->first;
357 syncer::StringOrdinal ChromeAppSorting::GetNaturalAppPageOrdinal() const {
358 if (ntp_ordinal_map_.empty())
359 return syncer::StringOrdinal::CreateInitialOrdinal();
361 for (PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
362 it != ntp_ordinal_map_.end(); ++it) {
363 if (CountItemsVisibleOnNtp(it->second) < kNaturalAppPageSize)
367 // Add a new page as all existing pages are full.
368 syncer::StringOrdinal last_element = ntp_ordinal_map_.rbegin()->first;
369 return last_element.CreateAfter();
372 syncer::StringOrdinal ChromeAppSorting::GetPageOrdinal(
373 const std::string& extension_id) const {
374 std::string raw_data;
375 // If the preference read fails then raw_data will still be unset and we will
376 // return an invalid StringOrdinal to signal that no page ordinal was found.
377 extension_scoped_prefs_->ReadPrefAsString(
378 extension_id, kPrefPageOrdinal, &raw_data);
379 return syncer::StringOrdinal(raw_data);
382 void ChromeAppSorting::SetPageOrdinal(
383 const std::string& extension_id,
384 const syncer::StringOrdinal& new_page_ordinal) {
385 // No work is required if the old and new values are the same.
386 if (new_page_ordinal.EqualsOrBothInvalid(GetPageOrdinal(extension_id)))
389 syncer::StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
390 RemoveOrdinalMapping(
391 extension_id, GetPageOrdinal(extension_id), app_launch_ordinal);
392 AddOrdinalMapping(extension_id, new_page_ordinal, app_launch_ordinal);
394 base::Value* new_value = new_page_ordinal.IsValid() ?
395 new base::StringValue(new_page_ordinal.ToInternalValue()) :
398 extension_scoped_prefs_->UpdateExtensionPref(
402 SyncIfNeeded(extension_id);
405 void ChromeAppSorting::ClearOrdinals(const std::string& extension_id) {
406 RemoveOrdinalMapping(extension_id,
407 GetPageOrdinal(extension_id),
408 GetAppLaunchOrdinal(extension_id));
410 extension_scoped_prefs_->UpdateExtensionPref(
411 extension_id, kPrefPageOrdinal, NULL);
412 extension_scoped_prefs_->UpdateExtensionPref(
413 extension_id, kPrefAppLaunchOrdinal, NULL);
416 int ChromeAppSorting::PageStringOrdinalAsInteger(
417 const syncer::StringOrdinal& page_ordinal) const {
418 if (!page_ordinal.IsValid())
421 PageOrdinalMap::const_iterator it = ntp_ordinal_map_.find(page_ordinal);
422 return it != ntp_ordinal_map_.end() ?
423 std::distance(ntp_ordinal_map_.begin(), it) : -1;
426 syncer::StringOrdinal ChromeAppSorting::PageIntegerAsStringOrdinal(
428 if (page_index < ntp_ordinal_map_.size()) {
429 PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
430 std::advance(it, page_index);
434 CreateOrdinalsIfNecessary(page_index + 1);
435 return ntp_ordinal_map_.rbegin()->first;
438 void ChromeAppSorting::MarkExtensionAsHidden(const std::string& extension_id) {
439 ntp_hidden_extensions_.insert(extension_id);
442 syncer::StringOrdinal ChromeAppSorting::GetMinOrMaxAppLaunchOrdinalsOnPage(
443 const syncer::StringOrdinal& target_page_ordinal,
444 AppLaunchOrdinalReturn return_type) const {
445 CHECK(target_page_ordinal.IsValid());
447 syncer::StringOrdinal return_value;
449 PageOrdinalMap::const_iterator page =
450 ntp_ordinal_map_.find(target_page_ordinal);
451 if (page != ntp_ordinal_map_.end()) {
452 const AppLaunchOrdinalMap& app_list = page->second;
454 if (app_list.empty())
455 return syncer::StringOrdinal();
457 if (return_type == ChromeAppSorting::MAX_ORDINAL)
458 return_value = app_list.rbegin()->first;
459 else if (return_type == ChromeAppSorting::MIN_ORDINAL)
460 return_value = app_list.begin()->first;
466 void ChromeAppSorting::InitializePageOrdinalMap(
467 const extensions::ExtensionIdList& extension_ids) {
468 for (extensions::ExtensionIdList::const_iterator ext_it =
469 extension_ids.begin(); ext_it != extension_ids.end(); ++ext_it) {
470 AddOrdinalMapping(*ext_it,
471 GetPageOrdinal(*ext_it),
472 GetAppLaunchOrdinal(*ext_it));
474 // Ensure that the web store app still isn't found in this list, since
475 // it is added after this loop.
476 DCHECK(*ext_it != extension_misc::kWebStoreAppId);
477 DCHECK(*ext_it != extension_misc::kChromeAppId);
480 // Include the Web Store App since it is displayed on the NTP.
481 syncer::StringOrdinal web_store_app_page =
482 GetPageOrdinal(extension_misc::kWebStoreAppId);
483 if (web_store_app_page.IsValid()) {
484 AddOrdinalMapping(extension_misc::kWebStoreAppId,
486 GetAppLaunchOrdinal(extension_misc::kWebStoreAppId));
488 // Include the Chrome App since it is displayed in the app launcher.
489 syncer::StringOrdinal chrome_app_page =
490 GetPageOrdinal(extension_misc::kChromeAppId);
491 if (chrome_app_page.IsValid()) {
492 AddOrdinalMapping(extension_misc::kChromeAppId,
494 GetAppLaunchOrdinal(extension_misc::kChromeAppId));
498 void ChromeAppSorting::AddOrdinalMapping(
499 const std::string& extension_id,
500 const syncer::StringOrdinal& page_ordinal,
501 const syncer::StringOrdinal& app_launch_ordinal) {
502 if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
505 ntp_ordinal_map_[page_ordinal].insert(
506 std::make_pair(app_launch_ordinal, extension_id));
509 void ChromeAppSorting::RemoveOrdinalMapping(
510 const std::string& extension_id,
511 const syncer::StringOrdinal& page_ordinal,
512 const syncer::StringOrdinal& app_launch_ordinal) {
513 if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
516 // Check that the page exists using find to prevent creating a new page
517 // if |page_ordinal| isn't a used page.
518 PageOrdinalMap::iterator page_map = ntp_ordinal_map_.find(page_ordinal);
519 if (page_map == ntp_ordinal_map_.end())
522 for (AppLaunchOrdinalMap::iterator it =
523 page_map->second.find(app_launch_ordinal);
524 it != page_map->second.end(); ++it) {
525 if (it->second == extension_id) {
526 page_map->second.erase(it);
532 void ChromeAppSorting::SyncIfNeeded(const std::string& extension_id) {
533 if (extension_sync_service_)
534 extension_sync_service_->SyncOrderingChange(extension_id);
537 void ChromeAppSorting::CreateDefaultOrdinals() {
538 if (default_ordinals_created_)
540 default_ordinals_created_ = true;
542 // The following defines the default order of apps.
543 #if defined(OS_CHROMEOS)
544 std::vector<std::string> app_ids;
545 chromeos::default_app_order::Get(&app_ids);
547 const char* kDefaultAppOrder[] = {
548 extension_misc::kChromeAppId,
549 extension_misc::kWebStoreAppId,
551 const std::vector<const char*> app_ids(
552 kDefaultAppOrder, kDefaultAppOrder + arraysize(kDefaultAppOrder));
555 syncer::StringOrdinal page_ordinal = CreateFirstAppPageOrdinal();
556 syncer::StringOrdinal app_launch_ordinal =
557 CreateFirstAppLaunchOrdinal(page_ordinal);
558 for (size_t i = 0; i < app_ids.size(); ++i) {
559 const std::string extension_id = app_ids[i];
560 default_ordinals_[extension_id].page_ordinal = page_ordinal;
561 default_ordinals_[extension_id].app_launch_ordinal = app_launch_ordinal;
562 app_launch_ordinal = app_launch_ordinal.CreateAfter();
566 bool ChromeAppSorting::GetDefaultOrdinals(
567 const std::string& extension_id,
568 syncer::StringOrdinal* page_ordinal,
569 syncer::StringOrdinal* app_launch_ordinal) {
570 CreateDefaultOrdinals();
571 AppOrdinalsMap::const_iterator it = default_ordinals_.find(extension_id);
572 if (it == default_ordinals_.end())
576 *page_ordinal = it->second.page_ordinal;
577 if (app_launch_ordinal)
578 *app_launch_ordinal = it->second.app_launch_ordinal;
582 syncer::StringOrdinal ChromeAppSorting::ResolveCollision(
583 const syncer::StringOrdinal& page_ordinal,
584 const syncer::StringOrdinal& app_launch_ordinal) const {
585 DCHECK(page_ordinal.IsValid() && app_launch_ordinal.IsValid());
587 PageOrdinalMap::const_iterator page_it = ntp_ordinal_map_.find(page_ordinal);
588 if (page_it == ntp_ordinal_map_.end())
589 return app_launch_ordinal;
591 const AppLaunchOrdinalMap& page = page_it->second;
592 AppLaunchOrdinalMap::const_iterator app_it = page.find(app_launch_ordinal);
593 if (app_it == page.end())
594 return app_launch_ordinal;
596 // Finds the next app launcher ordinal. This is done by the following loop
597 // because this function could be called before FixNTPOrdinalCollisions and
598 // thus |page| might contains multiple entries with the same app launch
599 // ordinal. See http://crbug.com/155603
600 while (app_it != page.end() && app_launch_ordinal.Equals(app_it->first))
603 // If there is no next after the collision, returns the next ordinal.
604 if (app_it == page.end())
605 return app_launch_ordinal.CreateAfter();
607 // Otherwise, returns the ordinal between the collision and the next ordinal.
608 return app_launch_ordinal.CreateBetween(app_it->first);
611 size_t ChromeAppSorting::CountItemsVisibleOnNtp(
612 const AppLaunchOrdinalMap& m) const {
614 for (AppLaunchOrdinalMap::const_iterator it = m.begin(); it != m.end();
616 const std::string& id = it->second;
617 if (ntp_hidden_extensions_.count(id) == 0)
623 } // namespace extensions