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