chrome/browser/extensions/chrome_app_sorting.cc

   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.
   4
   5 #include "chrome/browser/extensions/chrome_app_sorting.h"
   6
   7 #include <algorithm>
   8 #include <vector>
   9
  10 #include "chrome/browser/chrome_notification_types.h"
  11 #include "chrome/browser/extensions/extension_sync_service.h"
  12 #include "chrome/browser/profiles/profile.h"
  13 #include "chrome/common/extensions/extension_constants.h"
  14 #include "content/public/browser/notification_service.h"
  15 #include "extensions/browser/extension_registry.h"
  16 #include "extensions/browser/extension_scoped_prefs.h"
  17 #include "extensions/browser/extension_system.h"
  18 #include "extensions/common/constants.h"
  19 #include "extensions/common/extension.h"
  20
  21 #if defined(OS_CHROMEOS)
  22 #include "chrome/browser/chromeos/extensions/default_app_order.h"
  23 #endif
  24
  25 namespace extensions {
  26
  27 namespace {
  28
  29 // The number of apps per page. This isn't a hard limit, but new apps installed
  30 // from the webstore will overflow onto a new page if this limit is reached.
  31 const size_t kNaturalAppPageSize = 18;
  32
  33 // A preference determining the order of which the apps appear on the NTP.
  34 const char kPrefAppLaunchIndexDeprecated[] = "app_launcher_index";
  35 const char kPrefAppLaunchOrdinal[] = "app_launcher_ordinal";
  36
  37 // A preference determining the page on which an app appears in the NTP.
  38 const char kPrefPageIndexDeprecated[] = "page_index";
  39 const char kPrefPageOrdinal[] = "page_ordinal";
  40
  41 }  // namespace
  42
  43 ////////////////////////////////////////////////////////////////////////////////
  44 // ChromeAppSorting::AppOrdinals
  45
  46 ChromeAppSorting::AppOrdinals::AppOrdinals() {}
  47
  48 ChromeAppSorting::AppOrdinals::~AppOrdinals() {}
  49
  50 ////////////////////////////////////////////////////////////////////////////////
  51 // ChromeAppSorting
  52
  53 ChromeAppSorting::ChromeAppSorting(content::BrowserContext* browser_context)
  54     : extension_scoped_prefs_(NULL),
  55       browser_context_(browser_context),
  56       default_ordinals_created_(false) {
  57 }
  58
  59 ChromeAppSorting::~ChromeAppSorting() {
  60 }
  61
  62 void ChromeAppSorting::SetExtensionScopedPrefs(ExtensionScopedPrefs* prefs) {
  63   extension_scoped_prefs_ = prefs;
  64 }
  65
  66 void ChromeAppSorting::CheckExtensionScopedPrefs() const {
  67   CHECK(extension_scoped_prefs_);
  68 }
  69
  70 void ChromeAppSorting::Initialize(
  71     const extensions::ExtensionIdList& extension_ids) {
  72   CHECK(extension_scoped_prefs_);
  73   InitializePageOrdinalMap(extension_ids);
  74
  75   MigrateAppIndex(extension_ids);
  76 }
  77
  78 void ChromeAppSorting::CreateOrdinalsIfNecessary(size_t minimum_size) {
  79   // Create StringOrdinal values as required to ensure |ntp_ordinal_map_| has at
  80   // least |minimum_size| entries.
  81   if (ntp_ordinal_map_.empty() && minimum_size > 0)
  82     ntp_ordinal_map_[syncer::StringOrdinal::CreateInitialOrdinal()];
  83
  84   while (ntp_ordinal_map_.size() < minimum_size) {
  85     syncer::StringOrdinal filler =
  86         ntp_ordinal_map_.rbegin()->first.CreateAfter();
  87     AppLaunchOrdinalMap empty_ordinal_map;
  88     ntp_ordinal_map_.insert(std::make_pair(filler, empty_ordinal_map));
  89   }
  90 }
  91
  92 void ChromeAppSorting::MigrateAppIndex(
  93     const extensions::ExtensionIdList& extension_ids) {
  94   if (extension_ids.empty())
  95     return;
  96
  97   // Convert all the page index values to page ordinals. If there are any
  98   // app launch values that need to be migrated, inserted them into a sorted
  99   // set to be dealt with later.
 100   typedef std::map<syncer::StringOrdinal, std::map<int, const std::string*>,
 101                    syncer::StringOrdinal::LessThanFn> AppPositionToIdMapping;
 102   AppPositionToIdMapping app_launches_to_convert;
 103   for (extensions::ExtensionIdList::const_iterator ext_id =
 104            extension_ids.begin(); ext_id != extension_ids.end(); ++ext_id) {
 105     int old_page_index = 0;
 106     syncer::StringOrdinal page = GetPageOrdinal(*ext_id);
 107     if (extension_scoped_prefs_->ReadPrefAsInteger(
 108             *ext_id,
 109             kPrefPageIndexDeprecated,
 110             &old_page_index)) {
 111       // Some extensions have invalid page index, so we don't
 112       // attempt to convert them.
 113       if (old_page_index < 0) {
 114         DLOG(WARNING) << "Extension " << *ext_id
 115                       << " has an invalid page index " << old_page_index
 116                       << ". Aborting attempt to convert its index.";
 117         break;
 118       }
 119
 120       CreateOrdinalsIfNecessary(static_cast<size_t>(old_page_index) + 1);
 121
 122       page = PageIntegerAsStringOrdinal(old_page_index);
 123       SetPageOrdinal(*ext_id, page);
 124       extension_scoped_prefs_->UpdateExtensionPref(
 125           *ext_id, kPrefPageIndexDeprecated, NULL);
 126     }
 127
 128     int old_app_launch_index = 0;
 129     if (extension_scoped_prefs_->ReadPrefAsInteger(
 130             *ext_id,
 131             kPrefAppLaunchIndexDeprecated,
 132             &old_app_launch_index)) {
 133       // We can't update the app launch index value yet, because we use
 134       // GetNextAppLaunchOrdinal to get the new ordinal value and it requires
 135       // all the ordinals with lower values to have already been migrated.
 136       // A valid page ordinal is also required because otherwise there is
 137       // no page to add the app to.
 138       if (page.IsValid())
 139         app_launches_to_convert[page][old_app_launch_index] = &*ext_id;
 140
 141       extension_scoped_prefs_->UpdateExtensionPref(
 142           *ext_id, kPrefAppLaunchIndexDeprecated, NULL);
 143     }
 144   }
 145
 146   // Remove any empty pages that may have been added. This shouldn't occur,
 147   // but double check here to prevent future problems with conversions between
 148   // integers and StringOrdinals.
 149   for (PageOrdinalMap::iterator it = ntp_ordinal_map_.begin();
 150        it != ntp_ordinal_map_.end();) {
 151     if (it->second.empty()) {
 152       PageOrdinalMap::iterator prev_it = it;
 153       ++it;
 154       ntp_ordinal_map_.erase(prev_it);
 155     } else {
 156       ++it;
 157     }
 158   }
 159
 160   if (app_launches_to_convert.empty())
 161     return;
 162
 163   // Create the new app launch ordinals and remove the old preferences. Since
 164   // the set is sorted, each time we migrate an apps index, we know that all of
 165   // the remaining apps will appear further down the NTP than it or on a
 166   // different page.
 167   for (AppPositionToIdMapping::const_iterator page_it =
 168            app_launches_to_convert.begin();
 169        page_it != app_launches_to_convert.end(); ++page_it) {
 170     syncer::StringOrdinal page = page_it->first;
 171     for (std::map<int, const std::string*>::const_iterator launch_it =
 172             page_it->second.begin(); launch_it != page_it->second.end();
 173         ++launch_it) {
 174       SetAppLaunchOrdinal(*(launch_it->second),
 175                           CreateNextAppLaunchOrdinal(page));
 176     }
 177   }
 178 }
 179
 180 void ChromeAppSorting::FixNTPOrdinalCollisions() {
 181   for (PageOrdinalMap::iterator page_it = ntp_ordinal_map_.begin();
 182        page_it != ntp_ordinal_map_.end(); ++page_it) {
 183     AppLaunchOrdinalMap& page = page_it->second;
 184
 185     AppLaunchOrdinalMap::iterator app_launch_it = page.begin();
 186     while (app_launch_it != page.end()) {
 187       int app_count = page.count(app_launch_it->first);
 188       if (app_count == 1) {
 189         ++app_launch_it;
 190         continue;
 191       }
 192
 193       syncer::StringOrdinal repeated_ordinal = app_launch_it->first;
 194
 195       // Sort the conflicting keys by their extension id, this is how
 196       // the order is decided.
 197       std::vector<std::string> conflicting_ids;
 198       for (int i = 0; i < app_count; ++i, ++app_launch_it)
 199         conflicting_ids.push_back(app_launch_it->second);
 200       std::sort(conflicting_ids.begin(), conflicting_ids.end());
 201
 202       syncer::StringOrdinal upper_bound_ordinal = app_launch_it == page.end() ?
 203           syncer::StringOrdinal() :
 204           app_launch_it->first;
 205       syncer::StringOrdinal lower_bound_ordinal = repeated_ordinal;
 206
 207       // Start at position 1 because the first extension can keep the conflicted
 208       // value.
 209       for (int i = 1; i < app_count; ++i) {
 210         syncer::StringOrdinal unique_app_launch;
 211         if (upper_bound_ordinal.IsValid()) {
 212           unique_app_launch =
 213               lower_bound_ordinal.CreateBetween(upper_bound_ordinal);
 214         } else {
 215           unique_app_launch = lower_bound_ordinal.CreateAfter();
 216         }
 217
 218         SetAppLaunchOrdinal(conflicting_ids[i], unique_app_launch);
 219         lower_bound_ordinal = unique_app_launch;
 220       }
 221     }
 222   }
 223
 224   content::NotificationService::current()->Notify(
 225       chrome::NOTIFICATION_APP_LAUNCHER_REORDERED,
 226       content::Source<ChromeAppSorting>(this),
 227       content::NotificationService::NoDetails());
 228 }
 229
 230 void ChromeAppSorting::EnsureValidOrdinals(
 231     const std::string& extension_id,
 232     const syncer::StringOrdinal& suggested_page) {
 233   syncer::StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
 234   if (!page_ordinal.IsValid()) {
 235     if (suggested_page.IsValid()) {
 236       page_ordinal = suggested_page;
 237     } else if (!GetDefaultOrdinals(extension_id, &page_ordinal, NULL) ||
 238         !page_ordinal.IsValid()) {
 239       page_ordinal = GetNaturalAppPageOrdinal();
 240     }
 241
 242     SetPageOrdinal(extension_id, page_ordinal);
 243   }
 244
 245   syncer::StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
 246   if (!app_launch_ordinal.IsValid()) {
 247     // If using default app launcher ordinal, make sure there is no collision.
 248     if (GetDefaultOrdinals(extension_id, NULL, &app_launch_ordinal) &&
 249         app_launch_ordinal.IsValid())
 250       app_launch_ordinal = ResolveCollision(page_ordinal, app_launch_ordinal);
 251     else
 252       app_launch_ordinal = CreateNextAppLaunchOrdinal(page_ordinal);
 253
 254     SetAppLaunchOrdinal(extension_id, app_launch_ordinal);
 255   }
 256 }
 257
 258 void ChromeAppSorting::OnExtensionMoved(
 259     const std::string& moved_extension_id,
 260     const std::string& predecessor_extension_id,
 261     const std::string& successor_extension_id) {
 262   // We only need to change the StringOrdinal if there are neighbours.
 263   if (!predecessor_extension_id.empty() || !successor_extension_id.empty()) {
 264     if (predecessor_extension_id.empty()) {
 265       // Only a successor.
 266       SetAppLaunchOrdinal(
 267           moved_extension_id,
 268           GetAppLaunchOrdinal(successor_extension_id).CreateBefore());
 269     } else if (successor_extension_id.empty()) {
 270       // Only a predecessor.
 271       SetAppLaunchOrdinal(
 272           moved_extension_id,
 273           GetAppLaunchOrdinal(predecessor_extension_id).CreateAfter());
 274     } else {
 275       // Both a successor and predecessor
 276       const syncer::StringOrdinal& predecessor_ordinal =
 277           GetAppLaunchOrdinal(predecessor_extension_id);
 278       const syncer::StringOrdinal& successor_ordinal =
 279           GetAppLaunchOrdinal(successor_extension_id);
 280       SetAppLaunchOrdinal(moved_extension_id,
 281                           predecessor_ordinal.CreateBetween(successor_ordinal));
 282     }
 283   }
 284
 285   SyncIfNeeded(moved_extension_id);
 286
 287   content::NotificationService::current()->Notify(
 288       chrome::NOTIFICATION_APP_LAUNCHER_REORDERED,
 289       content::Source<ChromeAppSorting>(this),
 290       content::Details<const std::string>(&moved_extension_id));
 291 }
 292
 293
 294 syncer::StringOrdinal ChromeAppSorting::GetAppLaunchOrdinal(
 295     const std::string& extension_id) const {
 296   std::string raw_value;
 297   // If the preference read fails then raw_value will still be unset and we
 298   // will return an invalid StringOrdinal to signal that no app launch ordinal
 299   // was found.
 300   extension_scoped_prefs_->ReadPrefAsString(
 301       extension_id, kPrefAppLaunchOrdinal, &raw_value);
 302   return syncer::StringOrdinal(raw_value);
 303 }
 304
 305 void ChromeAppSorting::SetAppLaunchOrdinal(
 306     const std::string& extension_id,
 307     const syncer::StringOrdinal& new_app_launch_ordinal) {
 308   // No work is required if the old and new values are the same.
 309   if (new_app_launch_ordinal.EqualsOrBothInvalid(
 310           GetAppLaunchOrdinal(extension_id))) {
 311     return;
 312   }
 313
 314   syncer::StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
 315   RemoveOrdinalMapping(
 316       extension_id, page_ordinal, GetAppLaunchOrdinal(extension_id));
 317   AddOrdinalMapping(extension_id, page_ordinal, new_app_launch_ordinal);
 318
 319   base::Value* new_value = new_app_launch_ordinal.IsValid() ?
 320       new base::StringValue(new_app_launch_ordinal.ToInternalValue()) :
 321       NULL;
 322
 323   extension_scoped_prefs_->UpdateExtensionPref(
 324       extension_id,
 325       kPrefAppLaunchOrdinal,
 326       new_value);
 327   SyncIfNeeded(extension_id);
 328 }
 329
 330 syncer::StringOrdinal ChromeAppSorting::CreateFirstAppLaunchOrdinal(
 331     const syncer::StringOrdinal& page_ordinal) const {
 332   const syncer::StringOrdinal& min_ordinal =
 333       GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
 334                                          ChromeAppSorting::MIN_ORDINAL);
 335
 336   if (min_ordinal.IsValid())
 337     return min_ordinal.CreateBefore();
 338   else
 339     return syncer::StringOrdinal::CreateInitialOrdinal();
 340 }
 341
 342 syncer::StringOrdinal ChromeAppSorting::CreateNextAppLaunchOrdinal(
 343     const syncer::StringOrdinal& page_ordinal) const {
 344   const syncer::StringOrdinal& max_ordinal =
 345       GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
 346                                          ChromeAppSorting::MAX_ORDINAL);
 347
 348   if (max_ordinal.IsValid())
 349     return max_ordinal.CreateAfter();
 350   else
 351     return syncer::StringOrdinal::CreateInitialOrdinal();
 352 }
 353
 354 syncer::StringOrdinal ChromeAppSorting::CreateFirstAppPageOrdinal() const {
 355   if (ntp_ordinal_map_.empty())
 356     return syncer::StringOrdinal::CreateInitialOrdinal();
 357
 358   return ntp_ordinal_map_.begin()->first;
 359 }
 360
 361 syncer::StringOrdinal ChromeAppSorting::GetNaturalAppPageOrdinal() const {
 362   if (ntp_ordinal_map_.empty())
 363     return syncer::StringOrdinal::CreateInitialOrdinal();
 364
 365   for (PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
 366        it != ntp_ordinal_map_.end(); ++it) {
 367     if (CountItemsVisibleOnNtp(it->second) < kNaturalAppPageSize)
 368       return it->first;
 369   }
 370
 371   // Add a new page as all existing pages are full.
 372   syncer::StringOrdinal last_element = ntp_ordinal_map_.rbegin()->first;
 373   return last_element.CreateAfter();
 374 }
 375
 376 syncer::StringOrdinal ChromeAppSorting::GetPageOrdinal(
 377     const std::string& extension_id) const {
 378   std::string raw_data;
 379   // If the preference read fails then raw_data will still be unset and we will
 380   // return an invalid StringOrdinal to signal that no page ordinal was found.
 381   extension_scoped_prefs_->ReadPrefAsString(
 382       extension_id, kPrefPageOrdinal, &raw_data);
 383   return syncer::StringOrdinal(raw_data);
 384 }
 385
 386 void ChromeAppSorting::SetPageOrdinal(
 387     const std::string& extension_id,
 388     const syncer::StringOrdinal& new_page_ordinal) {
 389   // No work is required if the old and new values are the same.
 390   if (new_page_ordinal.EqualsOrBothInvalid(GetPageOrdinal(extension_id)))
 391     return;
 392
 393   syncer::StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
 394   RemoveOrdinalMapping(
 395       extension_id, GetPageOrdinal(extension_id), app_launch_ordinal);
 396   AddOrdinalMapping(extension_id, new_page_ordinal, app_launch_ordinal);
 397
 398   base::Value* new_value = new_page_ordinal.IsValid() ?
 399       new base::StringValue(new_page_ordinal.ToInternalValue()) :
 400       NULL;
 401
 402   extension_scoped_prefs_->UpdateExtensionPref(
 403       extension_id,
 404       kPrefPageOrdinal,
 405       new_value);
 406   SyncIfNeeded(extension_id);
 407 }
 408
 409 void ChromeAppSorting::ClearOrdinals(const std::string& extension_id) {
 410   RemoveOrdinalMapping(extension_id,
 411                        GetPageOrdinal(extension_id),
 412                        GetAppLaunchOrdinal(extension_id));
 413
 414   extension_scoped_prefs_->UpdateExtensionPref(
 415       extension_id, kPrefPageOrdinal, NULL);
 416   extension_scoped_prefs_->UpdateExtensionPref(
 417       extension_id, kPrefAppLaunchOrdinal, NULL);
 418 }
 419
 420 int ChromeAppSorting::PageStringOrdinalAsInteger(
 421     const syncer::StringOrdinal& page_ordinal) const {
 422   if (!page_ordinal.IsValid())
 423     return -1;
 424
 425   PageOrdinalMap::const_iterator it = ntp_ordinal_map_.find(page_ordinal);
 426   return it != ntp_ordinal_map_.end() ?
 427       std::distance(ntp_ordinal_map_.begin(), it) : -1;
 428 }
 429
 430 syncer::StringOrdinal ChromeAppSorting::PageIntegerAsStringOrdinal(
 431     size_t page_index) {
 432   if (page_index < ntp_ordinal_map_.size()) {
 433     PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
 434     std::advance(it, page_index);
 435     return it->first;
 436   }
 437
 438   CreateOrdinalsIfNecessary(page_index + 1);
 439   return ntp_ordinal_map_.rbegin()->first;
 440 }
 441
 442 void ChromeAppSorting::SetExtensionVisible(const std::string& extension_id,
 443                                            bool visible) {
 444   if (visible)
 445     ntp_hidden_extensions_.erase(extension_id);
 446   else
 447     ntp_hidden_extensions_.insert(extension_id);
 448 }
 449
 450 syncer::StringOrdinal ChromeAppSorting::GetMinOrMaxAppLaunchOrdinalsOnPage(
 451     const syncer::StringOrdinal& target_page_ordinal,
 452     AppLaunchOrdinalReturn return_type) const {
 453   CHECK(target_page_ordinal.IsValid());
 454
 455   syncer::StringOrdinal return_value;
 456
 457   PageOrdinalMap::const_iterator page =
 458       ntp_ordinal_map_.find(target_page_ordinal);
 459   if (page != ntp_ordinal_map_.end()) {
 460     const AppLaunchOrdinalMap& app_list = page->second;
 461
 462     if (app_list.empty())
 463       return syncer::StringOrdinal();
 464
 465     if (return_type == ChromeAppSorting::MAX_ORDINAL)
 466       return_value = app_list.rbegin()->first;
 467     else if (return_type == ChromeAppSorting::MIN_ORDINAL)
 468       return_value = app_list.begin()->first;
 469   }
 470
 471   return return_value;
 472 }
 473
 474 void ChromeAppSorting::InitializePageOrdinalMap(
 475     const extensions::ExtensionIdList& extension_ids) {
 476   // TODO(mgiuca): Added this CHECK to try and diagnose http://crbug.com/476648.
 477   // Remove it after the investigation is concluded.
 478   CHECK(extension_scoped_prefs_);
 479   for (extensions::ExtensionIdList::const_iterator ext_it =
 480            extension_ids.begin(); ext_it != extension_ids.end(); ++ext_it) {
 481     AddOrdinalMapping(*ext_it,
 482                       GetPageOrdinal(*ext_it),
 483                       GetAppLaunchOrdinal(*ext_it));
 484
 485     // Ensure that the web store app still isn't found in this list, since
 486     // it is added after this loop.
 487     DCHECK(*ext_it != extensions::kWebStoreAppId);
 488     DCHECK(*ext_it != extension_misc::kChromeAppId);
 489   }
 490
 491   // Include the Web Store App since it is displayed on the NTP.
 492   syncer::StringOrdinal web_store_app_page =
 493       GetPageOrdinal(extensions::kWebStoreAppId);
 494   if (web_store_app_page.IsValid()) {
 495     AddOrdinalMapping(extensions::kWebStoreAppId,
 496                       web_store_app_page,
 497                       GetAppLaunchOrdinal(extensions::kWebStoreAppId));
 498   }
 499   // Include the Chrome App since it is displayed in the app launcher.
 500   syncer::StringOrdinal chrome_app_page =
 501       GetPageOrdinal(extension_misc::kChromeAppId);
 502   if (chrome_app_page.IsValid()) {
 503     AddOrdinalMapping(extension_misc::kChromeAppId,
 504                       chrome_app_page,
 505                       GetAppLaunchOrdinal(extension_misc::kChromeAppId));
 506   }
 507 }
 508
 509 void ChromeAppSorting::AddOrdinalMapping(
 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())
 514     return;
 515
 516   ntp_ordinal_map_[page_ordinal].insert(
 517       std::make_pair(app_launch_ordinal, extension_id));
 518 }
 519
 520 void ChromeAppSorting::RemoveOrdinalMapping(
 521     const std::string& extension_id,
 522     const syncer::StringOrdinal& page_ordinal,
 523     const syncer::StringOrdinal& app_launch_ordinal) {
 524   if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
 525     return;
 526
 527   // Check that the page exists using find to prevent creating a new page
 528   // if |page_ordinal| isn't a used page.
 529   PageOrdinalMap::iterator page_map = ntp_ordinal_map_.find(page_ordinal);
 530   if (page_map == ntp_ordinal_map_.end())
 531     return;
 532
 533   for (AppLaunchOrdinalMap::iterator it =
 534            page_map->second.find(app_launch_ordinal);
 535        it != page_map->second.end(); ++it) {
 536     if (it->second == extension_id) {
 537       page_map->second.erase(it);
 538       break;
 539     }
 540   }
 541 }
 542
 543 void ChromeAppSorting::SyncIfNeeded(const std::string& extension_id) {
 544   // Can be null in tests.
 545   if (!browser_context_)
 546     return;
 547
 548   ExtensionRegistry* registry = ExtensionRegistry::Get(browser_context_);
 549   const Extension* extension = registry->GetInstalledExtension(extension_id);
 550   if (extension) {
 551     Profile* profile = Profile::FromBrowserContext(browser_context_);
 552     ExtensionSyncService::Get(profile)->SyncExtensionChangeIfNeeded(*extension);
 553   }
 554 }
 555
 556 void ChromeAppSorting::CreateDefaultOrdinals() {
 557   if (default_ordinals_created_)
 558     return;
 559   default_ordinals_created_ = true;
 560
 561   // The following defines the default order of apps.
 562 #if defined(OS_CHROMEOS)
 563   std::vector<std::string> app_ids;
 564   chromeos::default_app_order::Get(&app_ids);
 565 #else
 566   const char* const kDefaultAppOrder[] = {
 567     extension_misc::kChromeAppId,
 568     extensions::kWebStoreAppId,
 569   };
 570   const std::vector<const char*> app_ids(
 571       kDefaultAppOrder, kDefaultAppOrder + arraysize(kDefaultAppOrder));
 572 #endif
 573
 574   syncer::StringOrdinal page_ordinal = CreateFirstAppPageOrdinal();
 575   syncer::StringOrdinal app_launch_ordinal =
 576       CreateFirstAppLaunchOrdinal(page_ordinal);
 577   for (size_t i = 0; i < app_ids.size(); ++i) {
 578     const std::string extension_id = app_ids[i];
 579     default_ordinals_[extension_id].page_ordinal = page_ordinal;
 580     default_ordinals_[extension_id].app_launch_ordinal = app_launch_ordinal;
 581     app_launch_ordinal = app_launch_ordinal.CreateAfter();
 582   }
 583 }
 584
 585 bool ChromeAppSorting::GetDefaultOrdinals(
 586     const std::string& extension_id,
 587     syncer::StringOrdinal* page_ordinal,
 588     syncer::StringOrdinal* app_launch_ordinal) {
 589   CreateDefaultOrdinals();
 590   AppOrdinalsMap::const_iterator it = default_ordinals_.find(extension_id);
 591   if (it == default_ordinals_.end())
 592     return false;
 593
 594   if (page_ordinal)
 595     *page_ordinal = it->second.page_ordinal;
 596   if (app_launch_ordinal)
 597     *app_launch_ordinal = it->second.app_launch_ordinal;
 598   return true;
 599 }
 600
 601 syncer::StringOrdinal ChromeAppSorting::ResolveCollision(
 602     const syncer::StringOrdinal& page_ordinal,
 603     const syncer::StringOrdinal& app_launch_ordinal) const {
 604   DCHECK(page_ordinal.IsValid() && app_launch_ordinal.IsValid());
 605
 606   PageOrdinalMap::const_iterator page_it = ntp_ordinal_map_.find(page_ordinal);
 607   if (page_it == ntp_ordinal_map_.end())
 608     return app_launch_ordinal;
 609
 610   const AppLaunchOrdinalMap& page = page_it->second;
 611   AppLaunchOrdinalMap::const_iterator app_it = page.find(app_launch_ordinal);
 612   if (app_it == page.end())
 613     return app_launch_ordinal;
 614
 615   // Finds the next app launcher ordinal. This is done by the following loop
 616   // because this function could be called before FixNTPOrdinalCollisions and
 617   // thus |page| might contains multiple entries with the same app launch
 618   // ordinal. See http://crbug.com/155603
 619   while (app_it != page.end() && app_launch_ordinal.Equals(app_it->first))
 620     ++app_it;
 621
 622   // If there is no next after the collision, returns the next ordinal.
 623   if (app_it == page.end())
 624     return app_launch_ordinal.CreateAfter();
 625
 626   // Otherwise, returns the ordinal between the collision and the next ordinal.
 627   return app_launch_ordinal.CreateBetween(app_it->first);
 628 }
 629
 630 size_t ChromeAppSorting::CountItemsVisibleOnNtp(
 631     const AppLaunchOrdinalMap& m) const {
 632   size_t result = 0;
 633   for (AppLaunchOrdinalMap::const_iterator it = m.begin(); it != m.end();
 634        ++it) {
 635     const std::string& id = it->second;
 636     if (ntp_hidden_extensions_.count(id) == 0)
 637       result++;
 638   }
 639   return result;
 640 }
 641
 642 }  // namespace extensions