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