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_scoped_prefs.h"
  12 #include "chrome/browser/extensions/extension_sync_service.h"
  13 #include "chrome/common/extensions/extension_constants.h"
  14 #include "content/public/browser/notification_service.h"
  15 #include "extensions/common/extension.h"
  16
  17 #if defined(OS_CHROMEOS)
  18 #include "chrome/browser/chromeos/extensions/default_app_order.h"
  19 #endif
  20
  21 namespace extensions {
  22
  23 namespace {
  24
  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;
  28
  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";
  32
  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";
  36
  37 }  // namespace
  38
  39 ////////////////////////////////////////////////////////////////////////////////
  40 // ChromeAppSorting::AppOrdinals
  41
  42 ChromeAppSorting::AppOrdinals::AppOrdinals() {}
  43
  44 ChromeAppSorting::AppOrdinals::~AppOrdinals() {}
  45
  46 ////////////////////////////////////////////////////////////////////////////////
  47 // ChromeAppSorting
  48
  49 ChromeAppSorting::ChromeAppSorting()
  50     : extension_scoped_prefs_(NULL),
  51       extension_sync_service_(NULL),
  52       default_ordinals_created_(false) {
  53 }
  54
  55 ChromeAppSorting::~ChromeAppSorting() {
  56 }
  57
  58 void ChromeAppSorting::SetExtensionScopedPrefs(ExtensionScopedPrefs* prefs) {
  59   extension_scoped_prefs_ = prefs;
  60 }
  61
  62 void ChromeAppSorting::SetExtensionSyncService(
  63     ExtensionSyncService* extension_sync_service) {
  64   extension_sync_service_ = extension_sync_service;
  65 }
  66
  67 void ChromeAppSorting::Initialize(
  68     const extensions::ExtensionIdList& extension_ids) {
  69   InitializePageOrdinalMap(extension_ids);
  70
  71   MigrateAppIndex(extension_ids);
  72 }
  73
  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()];
  79
  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));
  85   }
  86 }
  87
  88 void ChromeAppSorting::MigrateAppIndex(
  89     const extensions::ExtensionIdList& extension_ids) {
  90   if (extension_ids.empty())
  91     return;
  92
  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(
 104             *ext_id,
 105             kPrefPageIndexDeprecated,
 106             &old_page_index)) {
 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.";
 113         break;
 114       }
 115
 116       CreateOrdinalsIfNecessary(static_cast<size_t>(old_page_index) + 1);
 117
 118       page = PageIntegerAsStringOrdinal(old_page_index);
 119       SetPageOrdinal(*ext_id, page);
 120       extension_scoped_prefs_->UpdateExtensionPref(
 121           *ext_id, kPrefPageIndexDeprecated, NULL);
 122     }
 123
 124     int old_app_launch_index = 0;
 125     if (extension_scoped_prefs_->ReadPrefAsInteger(
 126             *ext_id,
 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.
 134       if (page.IsValid())
 135         app_launches_to_convert[page][old_app_launch_index] = &*ext_id;
 136
 137       extension_scoped_prefs_->UpdateExtensionPref(
 138           *ext_id, kPrefAppLaunchIndexDeprecated, NULL);
 139     }
 140   }
 141
 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;
 149       ++it;
 150       ntp_ordinal_map_.erase(prev_it);
 151     } else {
 152       ++it;
 153     }
 154   }
 155
 156   if (app_launches_to_convert.empty())
 157     return;
 158
 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
 162   // different page.
 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();
 169         ++launch_it) {
 170       SetAppLaunchOrdinal(*(launch_it->second),
 171                           CreateNextAppLaunchOrdinal(page));
 172     }
 173   }
 174 }
 175
 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;
 180
 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) {
 185         ++app_launch_it;
 186         continue;
 187       }
 188
 189       syncer::StringOrdinal repeated_ordinal = app_launch_it->first;
 190
 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());
 197
 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;
 202
 203       // Start at position 1 because the first extension can keep the conflicted
 204       // value.
 205       for (int i = 1; i < app_count; ++i) {
 206         syncer::StringOrdinal unique_app_launch;
 207         if (upper_bound_ordinal.IsValid()) {
 208           unique_app_launch =
 209               lower_bound_ordinal.CreateBetween(upper_bound_ordinal);
 210         } else {
 211           unique_app_launch = lower_bound_ordinal.CreateAfter();
 212         }
 213
 214         SetAppLaunchOrdinal(conflicting_ids[i], unique_app_launch);
 215         lower_bound_ordinal = unique_app_launch;
 216       }
 217     }
 218   }
 219
 220   content::NotificationService::current()->Notify(
 221       chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
 222       content::Source<ChromeAppSorting>(this),
 223       content::NotificationService::NoDetails());
 224 }
 225
 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();
 236     }
 237
 238     SetPageOrdinal(extension_id, page_ordinal);
 239   }
 240
 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);
 247     else
 248       app_launch_ordinal = CreateNextAppLaunchOrdinal(page_ordinal);
 249
 250     SetAppLaunchOrdinal(extension_id, app_launch_ordinal);
 251   }
 252 }
 253
 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()) {
 261       // Only a successor.
 262       SetAppLaunchOrdinal(
 263           moved_extension_id,
 264           GetAppLaunchOrdinal(successor_extension_id).CreateBefore());
 265     } else if (successor_extension_id.empty()) {
 266       // Only a predecessor.
 267       SetAppLaunchOrdinal(
 268           moved_extension_id,
 269           GetAppLaunchOrdinal(predecessor_extension_id).CreateAfter());
 270     } else {
 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));
 278     }
 279   }
 280
 281   content::NotificationService::current()->Notify(
 282       chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
 283       content::Source<ChromeAppSorting>(this),
 284       content::Details<const std::string>(&moved_extension_id));
 285 }
 286
 287
 288 syncer::StringOrdinal ChromeAppSorting::GetAppLaunchOrdinal(
 289     const std::string& extension_id) const {
 290   std::string raw_value;
 291   // If the preference read fails then raw_value will still be unset and we
 292   // will return an invalid StringOrdinal to signal that no app launch ordinal
 293   // was found.
 294   extension_scoped_prefs_->ReadPrefAsString(
 295       extension_id, kPrefAppLaunchOrdinal, &raw_value);
 296   return syncer::StringOrdinal(raw_value);
 297 }
 298
 299 void ChromeAppSorting::SetAppLaunchOrdinal(
 300     const std::string& extension_id,
 301     const syncer::StringOrdinal& new_app_launch_ordinal) {
 302   // No work is required if the old and new values are the same.
 303   if (new_app_launch_ordinal.EqualsOrBothInvalid(
 304           GetAppLaunchOrdinal(extension_id))) {
 305     return;
 306   }
 307
 308   syncer::StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
 309   RemoveOrdinalMapping(
 310       extension_id, page_ordinal, GetAppLaunchOrdinal(extension_id));
 311   AddOrdinalMapping(extension_id, page_ordinal, new_app_launch_ordinal);
 312
 313   base::Value* new_value = new_app_launch_ordinal.IsValid() ?
 314       new base::StringValue(new_app_launch_ordinal.ToInternalValue()) :
 315       NULL;
 316
 317   extension_scoped_prefs_->UpdateExtensionPref(
 318       extension_id,
 319       kPrefAppLaunchOrdinal,
 320       new_value);
 321   SyncIfNeeded(extension_id);
 322 }
 323
 324 syncer::StringOrdinal ChromeAppSorting::CreateFirstAppLaunchOrdinal(
 325     const syncer::StringOrdinal& page_ordinal) const {
 326   const syncer::StringOrdinal& min_ordinal =
 327       GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
 328                                          ChromeAppSorting::MIN_ORDINAL);
 329
 330   if (min_ordinal.IsValid())
 331     return min_ordinal.CreateBefore();
 332   else
 333     return syncer::StringOrdinal::CreateInitialOrdinal();
 334 }
 335
 336 syncer::StringOrdinal ChromeAppSorting::CreateNextAppLaunchOrdinal(
 337     const syncer::StringOrdinal& page_ordinal) const {
 338   const syncer::StringOrdinal& max_ordinal =
 339       GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
 340                                          ChromeAppSorting::MAX_ORDINAL);
 341
 342   if (max_ordinal.IsValid())
 343     return max_ordinal.CreateAfter();
 344   else
 345     return syncer::StringOrdinal::CreateInitialOrdinal();
 346 }
 347
 348 syncer::StringOrdinal ChromeAppSorting::CreateFirstAppPageOrdinal() const {
 349   if (ntp_ordinal_map_.empty())
 350     return syncer::StringOrdinal::CreateInitialOrdinal();
 351
 352   return ntp_ordinal_map_.begin()->first;
 353 }
 354
 355 syncer::StringOrdinal ChromeAppSorting::GetNaturalAppPageOrdinal() const {
 356   if (ntp_ordinal_map_.empty())
 357     return syncer::StringOrdinal::CreateInitialOrdinal();
 358
 359   for (PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
 360        it != ntp_ordinal_map_.end(); ++it) {
 361     if (CountItemsVisibleOnNtp(it->second) < kNaturalAppPageSize)
 362       return it->first;
 363   }
 364
 365   // Add a new page as all existing pages are full.
 366   syncer::StringOrdinal last_element = ntp_ordinal_map_.rbegin()->first;
 367   return last_element.CreateAfter();
 368 }
 369
 370 syncer::StringOrdinal ChromeAppSorting::GetPageOrdinal(
 371     const std::string& extension_id) const {
 372   std::string raw_data;
 373   // If the preference read fails then raw_data will still be unset and we will
 374   // return an invalid StringOrdinal to signal that no page ordinal was found.
 375   extension_scoped_prefs_->ReadPrefAsString(
 376       extension_id, kPrefPageOrdinal, &raw_data);
 377   return syncer::StringOrdinal(raw_data);
 378 }
 379
 380 void ChromeAppSorting::SetPageOrdinal(
 381     const std::string& extension_id,
 382     const syncer::StringOrdinal& new_page_ordinal) {
 383   // No work is required if the old and new values are the same.
 384   if (new_page_ordinal.EqualsOrBothInvalid(GetPageOrdinal(extension_id)))
 385     return;
 386
 387   syncer::StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
 388   RemoveOrdinalMapping(
 389       extension_id, GetPageOrdinal(extension_id), app_launch_ordinal);
 390   AddOrdinalMapping(extension_id, new_page_ordinal, app_launch_ordinal);
 391
 392   base::Value* new_value = new_page_ordinal.IsValid() ?
 393       new base::StringValue(new_page_ordinal.ToInternalValue()) :
 394       NULL;
 395
 396   extension_scoped_prefs_->UpdateExtensionPref(
 397       extension_id,
 398       kPrefPageOrdinal,
 399       new_value);
 400   SyncIfNeeded(extension_id);
 401 }
 402
 403 void ChromeAppSorting::ClearOrdinals(const std::string& extension_id) {
 404   RemoveOrdinalMapping(extension_id,
 405                        GetPageOrdinal(extension_id),
 406                        GetAppLaunchOrdinal(extension_id));
 407
 408   extension_scoped_prefs_->UpdateExtensionPref(
 409       extension_id, kPrefPageOrdinal, NULL);
 410   extension_scoped_prefs_->UpdateExtensionPref(
 411       extension_id, kPrefAppLaunchOrdinal, NULL);
 412 }
 413
 414 int ChromeAppSorting::PageStringOrdinalAsInteger(
 415     const syncer::StringOrdinal& page_ordinal) const {
 416   if (!page_ordinal.IsValid())
 417     return -1;
 418
 419   PageOrdinalMap::const_iterator it = ntp_ordinal_map_.find(page_ordinal);
 420   return it != ntp_ordinal_map_.end() ?
 421       std::distance(ntp_ordinal_map_.begin(), it) : -1;
 422 }
 423
 424 syncer::StringOrdinal ChromeAppSorting::PageIntegerAsStringOrdinal(
 425     size_t page_index) {
 426   if (page_index < ntp_ordinal_map_.size()) {
 427     PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
 428     std::advance(it, page_index);
 429     return it->first;
 430   }
 431
 432   CreateOrdinalsIfNecessary(page_index + 1);
 433   return ntp_ordinal_map_.rbegin()->first;
 434 }
 435
 436 void ChromeAppSorting::MarkExtensionAsHidden(const std::string& extension_id) {
 437   ntp_hidden_extensions_.insert(extension_id);
 438 }
 439
 440 syncer::StringOrdinal ChromeAppSorting::GetMinOrMaxAppLaunchOrdinalsOnPage(
 441     const syncer::StringOrdinal& target_page_ordinal,
 442     AppLaunchOrdinalReturn return_type) const {
 443   CHECK(target_page_ordinal.IsValid());
 444
 445   syncer::StringOrdinal return_value;
 446
 447   PageOrdinalMap::const_iterator page =
 448       ntp_ordinal_map_.find(target_page_ordinal);
 449   if (page != ntp_ordinal_map_.end()) {
 450     const AppLaunchOrdinalMap& app_list = page->second;
 451
 452     if (app_list.empty())
 453       return syncer::StringOrdinal();
 454
 455     if (return_type == ChromeAppSorting::MAX_ORDINAL)
 456       return_value = app_list.rbegin()->first;
 457     else if (return_type == ChromeAppSorting::MIN_ORDINAL)
 458       return_value = app_list.begin()->first;
 459   }
 460
 461   return return_value;
 462 }
 463
 464 void ChromeAppSorting::InitializePageOrdinalMap(
 465     const extensions::ExtensionIdList& extension_ids) {
 466   for (extensions::ExtensionIdList::const_iterator ext_it =
 467            extension_ids.begin(); ext_it != extension_ids.end(); ++ext_it) {
 468     AddOrdinalMapping(*ext_it,
 469                       GetPageOrdinal(*ext_it),
 470                       GetAppLaunchOrdinal(*ext_it));
 471
 472     // Ensure that the web store app still isn't found in this list, since
 473     // it is added after this loop.
 474     DCHECK(*ext_it != extension_misc::kWebStoreAppId);
 475     DCHECK(*ext_it != extension_misc::kChromeAppId);
 476   }
 477
 478   // Include the Web Store App since it is displayed on the NTP.
 479   syncer::StringOrdinal web_store_app_page =
 480       GetPageOrdinal(extension_misc::kWebStoreAppId);
 481   if (web_store_app_page.IsValid()) {
 482     AddOrdinalMapping(extension_misc::kWebStoreAppId,
 483                       web_store_app_page,
 484                       GetAppLaunchOrdinal(extension_misc::kWebStoreAppId));
 485   }
 486   // Include the Chrome App since it is displayed in the app launcher.
 487   syncer::StringOrdinal chrome_app_page =
 488       GetPageOrdinal(extension_misc::kChromeAppId);
 489   if (chrome_app_page.IsValid()) {
 490     AddOrdinalMapping(extension_misc::kChromeAppId,
 491                       chrome_app_page,
 492                       GetAppLaunchOrdinal(extension_misc::kChromeAppId));
 493   }
 494 }
 495
 496 void ChromeAppSorting::AddOrdinalMapping(
 497     const std::string& extension_id,
 498     const syncer::StringOrdinal& page_ordinal,
 499     const syncer::StringOrdinal& app_launch_ordinal) {
 500   if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
 501     return;
 502
 503   ntp_ordinal_map_[page_ordinal].insert(
 504       std::make_pair(app_launch_ordinal, extension_id));
 505 }
 506
 507 void ChromeAppSorting::RemoveOrdinalMapping(
 508     const std::string& extension_id,
 509     const syncer::StringOrdinal& page_ordinal,
 510     const syncer::StringOrdinal& app_launch_ordinal) {
 511   if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
 512     return;
 513
 514   // Check that the page exists using find to prevent creating a new page
 515   // if |page_ordinal| isn't a used page.
 516   PageOrdinalMap::iterator page_map = ntp_ordinal_map_.find(page_ordinal);
 517   if (page_map == ntp_ordinal_map_.end())
 518     return;
 519
 520   for (AppLaunchOrdinalMap::iterator it =
 521            page_map->second.find(app_launch_ordinal);
 522        it != page_map->second.end(); ++it) {
 523     if (it->second == extension_id) {
 524       page_map->second.erase(it);
 525       break;
 526     }
 527   }
 528 }
 529
 530 void ChromeAppSorting::SyncIfNeeded(const std::string& extension_id) {
 531   if (extension_sync_service_)
 532     extension_sync_service_->SyncOrderingChange(extension_id);
 533 }
 534
 535 void ChromeAppSorting::CreateDefaultOrdinals() {
 536   if (default_ordinals_created_)
 537     return;
 538   default_ordinals_created_ = true;
 539
 540   // The following defines the default order of apps.
 541 #if defined(OS_CHROMEOS)
 542   std::vector<std::string> app_ids;
 543   chromeos::default_app_order::Get(&app_ids);
 544 #else
 545   const char* kDefaultAppOrder[] = {
 546     extension_misc::kChromeAppId,
 547     extension_misc::kWebStoreAppId,
 548   };
 549   const std::vector<const char*> app_ids(
 550       kDefaultAppOrder, kDefaultAppOrder + arraysize(kDefaultAppOrder));
 551 #endif
 552
 553   syncer::StringOrdinal page_ordinal = CreateFirstAppPageOrdinal();
 554   syncer::StringOrdinal app_launch_ordinal =
 555       CreateFirstAppLaunchOrdinal(page_ordinal);
 556   for (size_t i = 0; i < app_ids.size(); ++i) {
 557     const std::string extension_id = app_ids[i];
 558     default_ordinals_[extension_id].page_ordinal = page_ordinal;
 559     default_ordinals_[extension_id].app_launch_ordinal = app_launch_ordinal;
 560     app_launch_ordinal = app_launch_ordinal.CreateAfter();
 561   }
 562 }
 563
 564 bool ChromeAppSorting::GetDefaultOrdinals(
 565     const std::string& extension_id,
 566     syncer::StringOrdinal* page_ordinal,
 567     syncer::StringOrdinal* app_launch_ordinal) {
 568   CreateDefaultOrdinals();
 569   AppOrdinalsMap::const_iterator it = default_ordinals_.find(extension_id);
 570   if (it == default_ordinals_.end())
 571     return false;
 572
 573   if (page_ordinal)
 574     *page_ordinal = it->second.page_ordinal;
 575   if (app_launch_ordinal)
 576     *app_launch_ordinal = it->second.app_launch_ordinal;
 577   return true;
 578 }
 579
 580 syncer::StringOrdinal ChromeAppSorting::ResolveCollision(
 581     const syncer::StringOrdinal& page_ordinal,
 582     const syncer::StringOrdinal& app_launch_ordinal) const {
 583   DCHECK(page_ordinal.IsValid() && app_launch_ordinal.IsValid());
 584
 585   PageOrdinalMap::const_iterator page_it = ntp_ordinal_map_.find(page_ordinal);
 586   if (page_it == ntp_ordinal_map_.end())
 587     return app_launch_ordinal;
 588
 589   const AppLaunchOrdinalMap& page = page_it->second;
 590   AppLaunchOrdinalMap::const_iterator app_it = page.find(app_launch_ordinal);
 591   if (app_it == page.end())
 592     return app_launch_ordinal;
 593
 594   // Finds the next app launcher ordinal. This is done by the following loop
 595   // because this function could be called before FixNTPOrdinalCollisions and
 596   // thus |page| might contains multiple entries with the same app launch
 597   // ordinal. See http://crbug.com/155603
 598   while (app_it != page.end() && app_launch_ordinal.Equals(app_it->first))
 599     ++app_it;
 600
 601   // If there is no next after the collision, returns the next ordinal.
 602   if (app_it == page.end())
 603     return app_launch_ordinal.CreateAfter();
 604
 605   // Otherwise, returns the ordinal between the collision and the next ordinal.
 606   return app_launch_ordinal.CreateBetween(app_it->first);
 607 }
 608
 609 size_t ChromeAppSorting::CountItemsVisibleOnNtp(
 610     const AppLaunchOrdinalMap& m) const {
 611   size_t result = 0;
 612   for (AppLaunchOrdinalMap::const_iterator it = m.begin(); it != m.end();
 613        ++it) {
 614     const std::string& id = it->second;
 615     if (ntp_hidden_extensions_.count(id) == 0)
 616       result++;
 617   }
 618   return result;
 619 }
 620
 621 }  // namespace extensions