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