src/chrome/browser/extensions/extension_sorting.cc

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