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 "chrome/browser/extensions/extension_scoped_prefs.h"
   8 #include "chrome/browser/extensions/extension_service.h"
   9 #include "chrome/common/chrome_notification_types.h"
  10 #include "content/public/browser/notification_service.h"
  11
  12 namespace {
  13
  14 // The number of apps per page. This isn't a hard limit, but new apps installed
  15 // from the webstore will overflow onto a new page if this limit is reached.
  16 const size_t kNaturalAppPageSize = 18;
  17
  18 // A preference determining the order of which the apps appear on the NTP.
  19 const char kPrefAppLaunchIndexDeprecated[] = "app_launcher_index";
  20 const char kPrefAppLaunchOrdinal[] = "app_launcher_ordinal";
  21
  22 // A preference determining the page on which an app appears in the NTP.
  23 const char kPrefPageIndexDeprecated[] = "page_index";
  24 const char kPrefPageOrdinal[] = "page_ordinal";
  25
  26 }  // namespace
  27
  28 ExtensionSorting::ExtensionSorting(ExtensionScopedPrefs* extension_scoped_prefs,
  29                                    PrefService* pref_service)
  30     : extension_scoped_prefs_(extension_scoped_prefs),
  31       pref_service_(pref_service) {
  32 }
  33
  34 ExtensionSorting::~ExtensionSorting() {
  35 }
  36
  37 void ExtensionSorting::Initialize(
  38     const ExtensionPrefs::ExtensionIdSet& extension_ids) {
  39   InitializePageOrdinalMap(extension_ids);
  40
  41   MigrateAppIndex(extension_ids);
  42 }
  43
  44 void ExtensionSorting::MigrateAppIndex(
  45     const ExtensionPrefs::ExtensionIdSet& extension_ids) {
  46   if (extension_ids.empty())
  47     return;
  48
  49   // Convert all the page index values to page ordinals. If there are any
  50   // app launch values that need to be migrated, inserted them into a sorted
  51   // set to be dealt with later.
  52   typedef std::map<StringOrdinal, std::map<int, const std::string*>,
  53       StringOrdinalLessThan> AppPositionToIdMapping;
  54   AppPositionToIdMapping app_launches_to_convert;
  55   for (ExtensionPrefs::ExtensionIdSet::const_iterator ext_id =
  56            extension_ids.begin(); ext_id != extension_ids.end(); ++ext_id) {
  57     int old_page_index = 0;
  58     StringOrdinal page = GetPageOrdinal(*ext_id);
  59     if (extension_scoped_prefs_->ReadExtensionPrefInteger(
  60             *ext_id,
  61             kPrefPageIndexDeprecated,
  62             &old_page_index)) {
  63       // Some extensions have invalid page index, so we don't
  64       // attempt to convert them.
  65       if (old_page_index < 0) {
  66         DLOG(WARNING) << "Extension " << *ext_id
  67                       << " has an invalid page index " << old_page_index
  68                       << ". Aborting attempt to convert its index.";
  69         break;
  70       }
  71
  72       // Since we require all earlier StringOrdinals to already exist in order
  73       // to properly convert from integers and we are iterating though them in
  74       // no given order, we create earlier StringOrdinal values as required.
  75       // This should be filled in by the time we are done with this loop.
  76       if (ntp_ordinal_map_.empty())
  77         ntp_ordinal_map_[StringOrdinal::CreateInitialOrdinal()];
  78       while (ntp_ordinal_map_.size()
  79              <= static_cast<size_t>(old_page_index)) {
  80         StringOrdinal earlier_page =
  81             ntp_ordinal_map_.rbegin()->first.CreateAfter();
  82         ntp_ordinal_map_[earlier_page];
  83       }
  84
  85       page = PageIntegerAsStringOrdinal(old_page_index);
  86       SetPageOrdinal(*ext_id, page);
  87       extension_scoped_prefs_->UpdateExtensionPref(
  88           *ext_id, kPrefPageIndexDeprecated, NULL);
  89     }
  90
  91     int old_app_launch_index = 0;
  92     if (extension_scoped_prefs_->ReadExtensionPrefInteger(
  93             *ext_id,
  94             kPrefAppLaunchIndexDeprecated,
  95             &old_app_launch_index)) {
  96       // We can't update the app launch index value yet, because we use
  97       // GetNextAppLaunchOrdinal to get the new ordinal value and it requires
  98       // all the ordinals with lower values to have already been migrated.
  99       // A valid page ordinal is also required because otherwise there is
 100       // no page to add the app to.
 101       if (page.IsValid())
 102         app_launches_to_convert[page][old_app_launch_index] = &*ext_id;
 103
 104       extension_scoped_prefs_->UpdateExtensionPref(
 105           *ext_id, kPrefAppLaunchIndexDeprecated, NULL);
 106     }
 107   }
 108
 109   // Remove any empty pages that may have been added. This shouldn't occur,
 110   // but double check here to prevent future problems with conversions between
 111   // integers and StringOrdinals.
 112   for (PageOrdinalMap::iterator it = ntp_ordinal_map_.begin();
 113        it != ntp_ordinal_map_.end();) {
 114     if (it->second.empty()) {
 115       PageOrdinalMap::iterator prev_it = it;
 116       ++it;
 117       ntp_ordinal_map_.erase(prev_it);
 118     } else {
 119       ++it;
 120     }
 121   }
 122
 123   if (app_launches_to_convert.empty())
 124     return;
 125
 126   // Create the new app launch ordinals and remove the old preferences. Since
 127   // the set is sorted, each time we migrate an apps index, we know that all of
 128   // the remaining apps will appear further down the NTP than it or on a
 129   // different page.
 130   for (AppPositionToIdMapping::const_iterator page_it =
 131            app_launches_to_convert.begin();
 132        page_it != app_launches_to_convert.end(); ++page_it) {
 133     StringOrdinal page = page_it->first;
 134     for (std::map<int, const std::string*>::const_iterator launch_it =
 135             page_it->second.begin(); launch_it != page_it->second.end();
 136         ++launch_it) {
 137       SetAppLaunchOrdinal(*(launch_it->second),
 138                           CreateNextAppLaunchOrdinal(page));
 139     }
 140   }
 141 }
 142
 143 void ExtensionSorting::FixNTPOrdinalCollisions() {
 144   for (PageOrdinalMap::iterator page_it = ntp_ordinal_map_.begin();
 145        page_it != ntp_ordinal_map_.end(); ++page_it) {
 146     AppLaunchOrdinalMap& page = page_it->second;
 147
 148     for (AppLaunchOrdinalMap::iterator app_launch_it = page.begin();
 149          app_launch_it != page.end(); ++app_launch_it) {
 150       int collisions = page.count(app_launch_it->first);
 151       if (collisions == 1)
 152         continue;
 153
 154       StringOrdinal repeated_ordinal = app_launch_it->first;
 155
 156       // Sort the conflicting keys by their extension id, this is how
 157       // the order is decided.
 158       std::vector<std::string> conflicting_ids;
 159       for (int i = 0; i < collisions; ++i, ++app_launch_it)
 160         conflicting_ids.push_back(app_launch_it->second);
 161       std::sort(conflicting_ids.begin(), conflicting_ids.end());
 162
 163       StringOrdinal upper_bound_ordinal = app_launch_it == page.end() ?
 164           StringOrdinal() :
 165           app_launch_it->first;
 166       StringOrdinal lower_bound_ordinal = repeated_ordinal;
 167
 168       // Start at position 1 because the first extension can keep the conflicted
 169       // value.
 170       for (int i = 1; i < collisions; ++i) {
 171         StringOrdinal unique_app_launch;
 172         if (upper_bound_ordinal.IsValid()) {
 173           unique_app_launch =
 174               lower_bound_ordinal.CreateBetween(upper_bound_ordinal);
 175         } else {
 176           unique_app_launch = lower_bound_ordinal.CreateAfter();
 177         }
 178
 179         SetAppLaunchOrdinal(conflicting_ids[i], unique_app_launch);
 180         lower_bound_ordinal = unique_app_launch;
 181       }
 182
 183       // This exit condition exists because the iterator may have moved to
 184       // the end of the map after getting the conflicting ids.
 185       if (app_launch_it == page.end())
 186         break;
 187     }
 188   }
 189 }
 190
 191 void ExtensionSorting::OnExtensionMoved(
 192     const std::string& moved_extension_id,
 193     const std::string& predecessor_extension_id,
 194     const std::string& successor_extension_id) {
 195   // If there are no neighbors then no changes are required, so we can return.
 196   if (predecessor_extension_id.empty() && successor_extension_id.empty())
 197     return;
 198
 199   if (predecessor_extension_id.empty()) {
 200     SetAppLaunchOrdinal(
 201         moved_extension_id,
 202         GetAppLaunchOrdinal(successor_extension_id).CreateBefore());
 203   } else if (successor_extension_id.empty()) {
 204     SetAppLaunchOrdinal(
 205         moved_extension_id,
 206         GetAppLaunchOrdinal(predecessor_extension_id).CreateAfter());
 207   } else {
 208     const StringOrdinal& predecessor_ordinal =
 209         GetAppLaunchOrdinal(predecessor_extension_id);
 210     const StringOrdinal& successor_ordinal =
 211         GetAppLaunchOrdinal(successor_extension_id);
 212     SetAppLaunchOrdinal(moved_extension_id,
 213                         predecessor_ordinal.CreateBetween(successor_ordinal));
 214   }
 215
 216   content::NotificationService::current()->Notify(
 217       chrome::NOTIFICATION_EXTENSION_LAUNCHER_REORDERED,
 218       content::Source<ExtensionSorting>(this),
 219       content::NotificationService::NoDetails());
 220 }
 221
 222
 223 StringOrdinal ExtensionSorting::GetAppLaunchOrdinal(
 224     const std::string& extension_id) const {
 225   std::string raw_value;
 226   // If the preference read fails then raw_value will still be unset and we
 227   // will return an invalid StringOrdinal to signal that no app launch ordinal
 228   // was found.
 229   extension_scoped_prefs_->ReadExtensionPrefString(
 230       extension_id, kPrefAppLaunchOrdinal, &raw_value);
 231   return StringOrdinal(raw_value);
 232 }
 233
 234 void ExtensionSorting::SetAppLaunchOrdinal(
 235     const std::string& extension_id,
 236     const StringOrdinal& new_app_launch_ordinal) {
 237   StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
 238   RemoveOrdinalMapping(
 239       extension_id, page_ordinal, GetAppLaunchOrdinal(extension_id));
 240   AddOrdinalMapping(extension_id, page_ordinal, new_app_launch_ordinal);
 241
 242   extension_scoped_prefs_->UpdateExtensionPref(
 243       extension_id,
 244       kPrefAppLaunchOrdinal,
 245       Value::CreateStringValue(new_app_launch_ordinal.ToString()));
 246 }
 247
 248 StringOrdinal ExtensionSorting::CreateFirstAppLaunchOrdinal(
 249     const StringOrdinal& page_ordinal) const {
 250   const StringOrdinal& min_ordinal =
 251       GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
 252                                          ExtensionSorting::MIN_ORDINAL);
 253
 254   if (min_ordinal.IsValid())
 255     return min_ordinal.CreateBefore();
 256   else
 257     return StringOrdinal::CreateInitialOrdinal();
 258 }
 259
 260 StringOrdinal ExtensionSorting::CreateNextAppLaunchOrdinal(
 261     const StringOrdinal& page_ordinal) const {
 262   const StringOrdinal& max_ordinal =
 263       GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
 264                                          ExtensionSorting::MAX_ORDINAL);
 265
 266   if (max_ordinal.IsValid())
 267     return max_ordinal.CreateAfter();
 268   else
 269     return StringOrdinal::CreateInitialOrdinal();
 270 }
 271
 272 StringOrdinal ExtensionSorting::CreateFirstAppPageOrdinal() const {
 273   const DictionaryValue* extensions = pref_service_->GetDictionary(
 274           ExtensionPrefs::kExtensionsPref);
 275   CHECK(extensions);
 276
 277   if (ntp_ordinal_map_.empty())
 278     return StringOrdinal::CreateInitialOrdinal();
 279
 280   return ntp_ordinal_map_.begin()->first;
 281 }
 282
 283 StringOrdinal ExtensionSorting::GetNaturalAppPageOrdinal() const {
 284   const DictionaryValue* extensions = pref_service_->GetDictionary(
 285           ExtensionPrefs::kExtensionsPref);
 286   CHECK(extensions);
 287
 288   if (ntp_ordinal_map_.empty())
 289     return StringOrdinal::CreateInitialOrdinal();
 290
 291   for (PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
 292        it != ntp_ordinal_map_.end(); ++it) {
 293     if (it->second.size() < kNaturalAppPageSize)
 294       return it->first;
 295   }
 296
 297   // Add a new page as all existing pages are full.
 298   StringOrdinal last_element = ntp_ordinal_map_.rbegin()->first;
 299   return last_element.CreateAfter();
 300 }
 301
 302 StringOrdinal ExtensionSorting::GetPageOrdinal(const std::string& extension_id)
 303     const {
 304   std::string raw_data;
 305   // If the preference read fails then raw_data will still be unset and we will
 306   // return an invalid StringOrdinal to signal that no page ordinal was found.
 307   extension_scoped_prefs_->ReadExtensionPrefString(
 308       extension_id, kPrefPageOrdinal, &raw_data);
 309   return StringOrdinal(raw_data);
 310 }
 311
 312 void ExtensionSorting::SetPageOrdinal(const std::string& extension_id,
 313                                     const StringOrdinal& new_page_ordinal) {
 314   StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
 315   RemoveOrdinalMapping(
 316       extension_id, GetPageOrdinal(extension_id), app_launch_ordinal);
 317   AddOrdinalMapping(extension_id, new_page_ordinal, app_launch_ordinal);
 318
 319   extension_scoped_prefs_->UpdateExtensionPref(
 320       extension_id,
 321       kPrefPageOrdinal,
 322       Value::CreateStringValue(new_page_ordinal.ToString()));
 323 }
 324
 325 void ExtensionSorting::ClearPageOrdinal(const std::string& extension_id) {
 326   RemoveOrdinalMapping(extension_id,
 327                        GetPageOrdinal(extension_id),
 328                        GetAppLaunchOrdinal(extension_id));
 329
 330   extension_scoped_prefs_->UpdateExtensionPref(
 331       extension_id, kPrefPageOrdinal, NULL);
 332 }
 333
 334 int ExtensionSorting::PageStringOrdinalAsInteger(
 335     const StringOrdinal& page_ordinal) const {
 336   if (!page_ordinal.IsValid())
 337     return -1;
 338
 339   PageOrdinalMap::const_iterator it = ntp_ordinal_map_.find(page_ordinal);
 340   if (it != ntp_ordinal_map_.end()) {
 341     return std::distance(ntp_ordinal_map_.begin(), it);
 342   } else {
 343     return -1;
 344   }
 345 }
 346
 347 StringOrdinal ExtensionSorting::PageIntegerAsStringOrdinal(size_t page_index)
 348     const {
 349   // We shouldn't have a page_index that is more than 1 position away from the
 350   // current end.
 351   CHECK_LE(page_index, ntp_ordinal_map_.size());
 352
 353   const DictionaryValue* extensions = pref_service_->GetDictionary(
 354           ExtensionPrefs::kExtensionsPref);
 355   if (!extensions)
 356     return StringOrdinal();
 357
 358   if (page_index < ntp_ordinal_map_.size()) {
 359     PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
 360     std::advance(it, page_index);
 361
 362     return it->first;
 363
 364   } else {
 365     if (ntp_ordinal_map_.empty())
 366       return StringOrdinal::CreateInitialOrdinal();
 367     else
 368       return ntp_ordinal_map_.rbegin()->first.CreateAfter();
 369   }
 370 }
 371
 372 StringOrdinal ExtensionSorting::GetMinOrMaxAppLaunchOrdinalsOnPage(
 373     const StringOrdinal& target_page_ordinal,
 374     AppLaunchOrdinalReturn return_type) const {
 375   const DictionaryValue* extensions = pref_service_->GetDictionary(
 376           ExtensionPrefs::kExtensionsPref);
 377   CHECK(extensions);
 378   CHECK(target_page_ordinal.IsValid());
 379
 380   StringOrdinal return_value;
 381   for (DictionaryValue::key_iterator ext_it = extensions->begin_keys();
 382        ext_it != extensions->end_keys(); ++ext_it) {
 383     const StringOrdinal& page_ordinal = GetPageOrdinal(*ext_it);
 384     if (page_ordinal.IsValid() && page_ordinal.Equal(target_page_ordinal)) {
 385       const StringOrdinal& app_launch_ordinal = GetAppLaunchOrdinal(*ext_it);
 386       if (app_launch_ordinal.IsValid()) {
 387         if (!return_value.IsValid())
 388           return_value = app_launch_ordinal;
 389         else if (return_type == ExtensionSorting::MIN_ORDINAL &&
 390                  app_launch_ordinal.LessThan(return_value))
 391           return_value = app_launch_ordinal;
 392         else if (return_type == ExtensionSorting::MAX_ORDINAL &&
 393                  app_launch_ordinal.GreaterThan(return_value))
 394           return_value = app_launch_ordinal;
 395       }
 396     }
 397   }
 398
 399   return return_value;
 400 }
 401
 402 void ExtensionSorting::InitializePageOrdinalMap(
 403     const ExtensionPrefs::ExtensionIdSet& extension_ids) {
 404   for (ExtensionPrefs::ExtensionIdSet::const_iterator ext_it =
 405            extension_ids.begin(); ext_it != extension_ids.end(); ++ext_it) {
 406     AddOrdinalMapping(*ext_it,
 407                       GetPageOrdinal(*ext_it),
 408                       GetAppLaunchOrdinal(*ext_it));
 409
 410     // Ensure that the web store app still isn't found in this list, since
 411     // it is added after this loop.
 412     DCHECK(*ext_it != extension_misc::kWebStoreAppId);
 413   }
 414
 415   // Include the Web Store App since it is displayed on the NTP.
 416   StringOrdinal web_store_app_page =
 417       GetPageOrdinal(extension_misc::kWebStoreAppId);
 418   if (web_store_app_page.IsValid()) {
 419     AddOrdinalMapping(extension_misc::kWebStoreAppId,
 420                       web_store_app_page,
 421                       GetAppLaunchOrdinal(extension_misc::kWebStoreAppId));
 422   }
 423 }
 424
 425 void ExtensionSorting::AddOrdinalMapping(
 426     const std::string& extension_id,
 427     const StringOrdinal& page_ordinal,
 428     const StringOrdinal& app_launch_ordinal) {
 429   if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
 430     return;
 431
 432   ntp_ordinal_map_[page_ordinal].insert(
 433       std::make_pair(app_launch_ordinal, extension_id));
 434 }
 435
 436 void ExtensionSorting::RemoveOrdinalMapping(
 437     const std::string& extension_id,
 438     const StringOrdinal& page_ordinal,
 439     const StringOrdinal& app_launch_ordinal) {
 440   if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
 441     return;
 442
 443   // Check that the page exists using find to prevent creating a new page
 444   // if |page_ordinal| isn't a used page.
 445   PageOrdinalMap::iterator page_map = ntp_ordinal_map_.find(page_ordinal);
 446   if (page_map == ntp_ordinal_map_.end())
 447     return;
 448
 449   for (AppLaunchOrdinalMap::iterator it =
 450            page_map->second.find(app_launch_ordinal);
 451        it != page_map->second.end(); ++it) {
 452     if (it->second == extension_id) {
 453       page_map->second.erase(it);
 454       break;
 455     }
 456   }
 457 }