chrome/browser/extensions/extension_sorting_unittest.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 <map>
   8
   9 #include "chrome/browser/extensions/extension_prefs_unittest.h"
  10 #include "extensions/common/manifest_constants.h"
  11 #include "sync/api/string_ordinal.h"
  12 #include "testing/gtest/include/gtest/gtest.h"
  13
  14 using extensions::Blacklist;
  15 using extensions::Extension;
  16 using extensions::Manifest;
  17
  18 namespace keys = extensions::manifest_keys;
  19
  20 class ExtensionSortingTest : public extensions::ExtensionPrefsTest {
  21  protected:
  22   ExtensionSorting* extension_sorting() {
  23     return prefs()->extension_sorting();
  24   }
  25 };
  26
  27 class ExtensionSortingAppLocation : public ExtensionSortingTest {
  28  public:
  29   virtual void Initialize() OVERRIDE {
  30     extension_ = prefs_.AddExtension("not_an_app");
  31     // Non-apps should not have any app launch ordinal or page ordinal.
  32     prefs()->OnExtensionInstalled(extension_.get(),
  33                                   Extension::ENABLED,
  34                                   Blacklist::NOT_BLACKLISTED,
  35                                   syncer::StringOrdinal());
  36   }
  37
  38   virtual void Verify() OVERRIDE {
  39     EXPECT_FALSE(
  40         extension_sorting()->GetAppLaunchOrdinal(extension_->id()).IsValid());
  41     EXPECT_FALSE(
  42         extension_sorting()->GetPageOrdinal(extension_->id()).IsValid());
  43   }
  44
  45  private:
  46   scoped_refptr<Extension> extension_;
  47 };
  48 TEST_F(ExtensionSortingAppLocation, ExtensionSortingAppLocation) {}
  49
  50 class ExtensionSortingAppLaunchOrdinal : public ExtensionSortingTest {
  51  public:
  52   virtual void Initialize() OVERRIDE {
  53     // No extensions yet.
  54     syncer::StringOrdinal page = syncer::StringOrdinal::CreateInitialOrdinal();
  55     EXPECT_TRUE(syncer::StringOrdinal::CreateInitialOrdinal().Equals(
  56         extension_sorting()->CreateNextAppLaunchOrdinal(page)));
  57
  58     extension_ = prefs_.AddApp("on_extension_installed");
  59     EXPECT_FALSE(prefs()->IsExtensionDisabled(extension_->id()));
  60     prefs()->OnExtensionInstalled(extension_.get(),
  61                                   Extension::ENABLED,
  62                                   Blacklist::NOT_BLACKLISTED,
  63                                   syncer::StringOrdinal());
  64   }
  65
  66   virtual void Verify() OVERRIDE {
  67     syncer::StringOrdinal launch_ordinal =
  68         extension_sorting()->GetAppLaunchOrdinal(extension_->id());
  69     syncer::StringOrdinal page_ordinal =
  70         syncer::StringOrdinal::CreateInitialOrdinal();
  71
  72     // Extension should have been assigned a valid StringOrdinal.
  73     EXPECT_TRUE(launch_ordinal.IsValid());
  74     EXPECT_TRUE(launch_ordinal.LessThan(
  75         extension_sorting()->CreateNextAppLaunchOrdinal(page_ordinal)));
  76     // Set a new launch ordinal of and verify it comes after.
  77     extension_sorting()->SetAppLaunchOrdinal(
  78         extension_->id(),
  79         extension_sorting()->CreateNextAppLaunchOrdinal(page_ordinal));
  80     syncer::StringOrdinal new_launch_ordinal =
  81         extension_sorting()->GetAppLaunchOrdinal(extension_->id());
  82     EXPECT_TRUE(launch_ordinal.LessThan(new_launch_ordinal));
  83
  84     // This extension doesn't exist, so it should return an invalid
  85     // StringOrdinal.
  86     syncer::StringOrdinal invalid_app_launch_ordinal =
  87         extension_sorting()->GetAppLaunchOrdinal("foo");
  88     EXPECT_FALSE(invalid_app_launch_ordinal.IsValid());
  89     EXPECT_EQ(-1, extension_sorting()->PageStringOrdinalAsInteger(
  90         invalid_app_launch_ordinal));
  91
  92     // The second page doesn't have any apps so its next launch ordinal should
  93     // be the first launch ordinal.
  94     syncer::StringOrdinal next_page = page_ordinal.CreateAfter();
  95     syncer::StringOrdinal next_page_app_launch_ordinal =
  96         extension_sorting()->CreateNextAppLaunchOrdinal(next_page);
  97     EXPECT_TRUE(next_page_app_launch_ordinal.Equals(
  98         extension_sorting()->CreateFirstAppLaunchOrdinal(next_page)));
  99   }
 100
 101  private:
 102   scoped_refptr<Extension> extension_;
 103 };
 104 TEST_F(ExtensionSortingAppLaunchOrdinal, ExtensionSortingAppLaunchOrdinal) {}
 105
 106 class ExtensionSortingPageOrdinal : public ExtensionSortingTest {
 107  public:
 108   virtual void Initialize() OVERRIDE {
 109     extension_ = prefs_.AddApp("page_ordinal");
 110     // Install with a page preference.
 111     first_page_ = syncer::StringOrdinal::CreateInitialOrdinal();
 112     prefs()->OnExtensionInstalled(extension_.get(),
 113                                   Extension::ENABLED,
 114                                   Blacklist::NOT_BLACKLISTED,
 115                                   first_page_);
 116     EXPECT_TRUE(first_page_.Equals(
 117         extension_sorting()->GetPageOrdinal(extension_->id())));
 118     EXPECT_EQ(0, extension_sorting()->PageStringOrdinalAsInteger(first_page_));
 119
 120     scoped_refptr<Extension> extension2 = prefs_.AddApp("page_ordinal_2");
 121     // Install without any page preference.
 122     prefs()->OnExtensionInstalled(extension2.get(),
 123                                   Extension::ENABLED,
 124                                   Blacklist::NOT_BLACKLISTED,
 125                                   syncer::StringOrdinal());
 126     EXPECT_TRUE(first_page_.Equals(
 127         extension_sorting()->GetPageOrdinal(extension2->id())));
 128   }
 129   virtual void Verify() OVERRIDE {
 130     // Set the page ordinal.
 131     syncer::StringOrdinal new_page = first_page_.CreateAfter();
 132     extension_sorting()->SetPageOrdinal(extension_->id(), new_page);
 133     // Verify the page ordinal.
 134     EXPECT_TRUE(
 135         new_page.Equals(extension_sorting()->GetPageOrdinal(extension_->id())));
 136     EXPECT_EQ(1, extension_sorting()->PageStringOrdinalAsInteger(new_page));
 137
 138     // This extension doesn't exist, so it should return an invalid
 139     // StringOrdinal.
 140     EXPECT_FALSE(extension_sorting()->GetPageOrdinal("foo").IsValid());
 141   }
 142
 143  private:
 144   syncer::StringOrdinal first_page_;
 145   scoped_refptr<Extension> extension_;
 146 };
 147 TEST_F(ExtensionSortingPageOrdinal, ExtensionSortingPageOrdinal) {}
 148
 149 // Ensure that ExtensionSorting is able to properly initialize off a set
 150 // of old page and app launch indices and properly convert them.
 151 class ExtensionSortingInitialize
 152     : public extensions::PrefsPrepopulatedTestBase {
 153  public:
 154   ExtensionSortingInitialize() {}
 155   virtual ~ExtensionSortingInitialize() {}
 156
 157   virtual void Initialize() OVERRIDE {
 158     // A preference determining the order of which the apps appear on the NTP.
 159     const char kPrefAppLaunchIndexDeprecated[] = "app_launcher_index";
 160     // A preference determining the page on which an app appears in the NTP.
 161     const char kPrefPageIndexDeprecated[] = "page_index";
 162
 163     // Setup the deprecated preferences.
 164     ExtensionScopedPrefs* scoped_prefs =
 165         static_cast<ExtensionScopedPrefs*>(prefs());
 166     scoped_prefs->UpdateExtensionPref(extension1()->id(),
 167                                       kPrefAppLaunchIndexDeprecated,
 168                                       new base::FundamentalValue(0));
 169     scoped_prefs->UpdateExtensionPref(extension1()->id(),
 170                                       kPrefPageIndexDeprecated,
 171                                       new base::FundamentalValue(0));
 172
 173     scoped_prefs->UpdateExtensionPref(extension2()->id(),
 174                                       kPrefAppLaunchIndexDeprecated,
 175                                       new base::FundamentalValue(1));
 176     scoped_prefs->UpdateExtensionPref(extension2()->id(),
 177                                       kPrefPageIndexDeprecated,
 178                                       new base::FundamentalValue(0));
 179
 180     scoped_prefs->UpdateExtensionPref(extension3()->id(),
 181                                       kPrefAppLaunchIndexDeprecated,
 182                                       new base::FundamentalValue(0));
 183     scoped_prefs->UpdateExtensionPref(extension3()->id(),
 184                                       kPrefPageIndexDeprecated,
 185                                       new base::FundamentalValue(1));
 186
 187     // We insert the ids in reserve order so that we have to deal with the
 188     // element on the 2nd page before the 1st page is seen.
 189     extensions::ExtensionIdList ids;
 190     ids.push_back(extension3()->id());
 191     ids.push_back(extension2()->id());
 192     ids.push_back(extension1()->id());
 193
 194     prefs()->extension_sorting()->Initialize(ids);
 195   }
 196   virtual void Verify() OVERRIDE {
 197     syncer::StringOrdinal first_ordinal =
 198         syncer::StringOrdinal::CreateInitialOrdinal();
 199     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 200
 201     EXPECT_TRUE(first_ordinal.Equals(
 202         extension_sorting->GetAppLaunchOrdinal(extension1()->id())));
 203     EXPECT_TRUE(first_ordinal.LessThan(
 204         extension_sorting->GetAppLaunchOrdinal(extension2()->id())));
 205     EXPECT_TRUE(first_ordinal.Equals(
 206         extension_sorting->GetAppLaunchOrdinal(extension3()->id())));
 207
 208     EXPECT_TRUE(first_ordinal.Equals(
 209         extension_sorting->GetPageOrdinal(extension1()->id())));
 210     EXPECT_TRUE(first_ordinal.Equals(
 211         extension_sorting->GetPageOrdinal(extension2()->id())));
 212     EXPECT_TRUE(first_ordinal.LessThan(
 213         extension_sorting->GetPageOrdinal(extension3()->id())));
 214   }
 215 };
 216 TEST_F(ExtensionSortingInitialize, ExtensionSortingInitialize) {}
 217
 218 // Make sure that initialization still works when no extensions are present
 219 // (i.e. make sure that the web store icon is still loaded into the map).
 220 class ExtensionSortingInitializeWithNoApps
 221     : public extensions::PrefsPrepopulatedTestBase {
 222  public:
 223   ExtensionSortingInitializeWithNoApps() {}
 224   virtual ~ExtensionSortingInitializeWithNoApps() {}
 225
 226   virtual void Initialize() OVERRIDE {
 227     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 228
 229     // Make sure that the web store has valid ordinals.
 230     syncer::StringOrdinal initial_ordinal =
 231         syncer::StringOrdinal::CreateInitialOrdinal();
 232     extension_sorting->SetPageOrdinal(extension_misc::kWebStoreAppId,
 233                                       initial_ordinal);
 234     extension_sorting->SetAppLaunchOrdinal(extension_misc::kWebStoreAppId,
 235                                            initial_ordinal);
 236
 237     extensions::ExtensionIdList ids;
 238     extension_sorting->Initialize(ids);
 239   }
 240   virtual void Verify() OVERRIDE {
 241     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 242
 243     syncer::StringOrdinal page =
 244         extension_sorting->GetPageOrdinal(extension_misc::kWebStoreAppId);
 245     EXPECT_TRUE(page.IsValid());
 246
 247     ExtensionSorting::PageOrdinalMap::iterator page_it =
 248         extension_sorting->ntp_ordinal_map_.find(page);
 249     EXPECT_TRUE(page_it != extension_sorting->ntp_ordinal_map_.end());
 250
 251     syncer::StringOrdinal app_launch =
 252         extension_sorting->GetPageOrdinal(extension_misc::kWebStoreAppId);
 253     EXPECT_TRUE(app_launch.IsValid());
 254
 255     ExtensionSorting::AppLaunchOrdinalMap::iterator app_launch_it =
 256         page_it->second.find(app_launch);
 257     EXPECT_TRUE(app_launch_it != page_it->second.end());
 258   }
 259 };
 260 TEST_F(ExtensionSortingInitializeWithNoApps,
 261        ExtensionSortingInitializeWithNoApps) {}
 262
 263 // Tests the application index to ordinal migration code for values that
 264 // shouldn't be converted. This should be removed when the migrate code
 265 // is taken out.
 266 // http://crbug.com/107376
 267 class ExtensionSortingMigrateAppIndexInvalid
 268     : public extensions::PrefsPrepopulatedTestBase {
 269  public:
 270   ExtensionSortingMigrateAppIndexInvalid() {}
 271   virtual ~ExtensionSortingMigrateAppIndexInvalid() {}
 272
 273   virtual void Initialize() OVERRIDE {
 274     // A preference determining the order of which the apps appear on the NTP.
 275     const char kPrefAppLaunchIndexDeprecated[] = "app_launcher_index";
 276     // A preference determining the page on which an app appears in the NTP.
 277     const char kPrefPageIndexDeprecated[] = "page_index";
 278
 279     // Setup the deprecated preference.
 280     ExtensionScopedPrefs* scoped_prefs =
 281         static_cast<ExtensionScopedPrefs*>(prefs());
 282     scoped_prefs->UpdateExtensionPref(extension1()->id(),
 283                                       kPrefAppLaunchIndexDeprecated,
 284                                       new base::FundamentalValue(0));
 285     scoped_prefs->UpdateExtensionPref(extension1()->id(),
 286                                       kPrefPageIndexDeprecated,
 287                                       new base::FundamentalValue(-1));
 288
 289     extensions::ExtensionIdList ids;
 290     ids.push_back(extension1()->id());
 291
 292     prefs()->extension_sorting()->Initialize(ids);
 293   }
 294   virtual void Verify() OVERRIDE {
 295     // Make sure that the invalid page_index wasn't converted over.
 296     EXPECT_FALSE(prefs()->extension_sorting()->GetAppLaunchOrdinal(
 297         extension1()->id()).IsValid());
 298   }
 299 };
 300 TEST_F(ExtensionSortingMigrateAppIndexInvalid,
 301        ExtensionSortingMigrateAppIndexInvalid) {}
 302
 303 class ExtensionSortingFixNTPCollisionsAllCollide
 304     : public extensions::PrefsPrepopulatedTestBase {
 305  public:
 306   ExtensionSortingFixNTPCollisionsAllCollide() {}
 307   virtual ~ExtensionSortingFixNTPCollisionsAllCollide() {}
 308
 309   virtual void Initialize() OVERRIDE {
 310     repeated_ordinal_ = syncer::StringOrdinal::CreateInitialOrdinal();
 311
 312     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 313
 314     extension_sorting->SetAppLaunchOrdinal(extension1()->id(),
 315                                            repeated_ordinal_);
 316     extension_sorting->SetPageOrdinal(extension1()->id(), repeated_ordinal_);
 317
 318     extension_sorting->SetAppLaunchOrdinal(extension2()->id(),
 319                                            repeated_ordinal_);
 320     extension_sorting->SetPageOrdinal(extension2()->id(), repeated_ordinal_);
 321
 322     extension_sorting->SetAppLaunchOrdinal(extension3()->id(),
 323                                            repeated_ordinal_);
 324     extension_sorting->SetPageOrdinal(extension3()->id(), repeated_ordinal_);
 325
 326     extension_sorting->FixNTPOrdinalCollisions();
 327   }
 328   virtual void Verify() OVERRIDE {
 329     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 330     syncer::StringOrdinal extension1_app_launch =
 331         extension_sorting->GetAppLaunchOrdinal(extension1()->id());
 332     syncer::StringOrdinal extension2_app_launch =
 333         extension_sorting->GetAppLaunchOrdinal(extension2()->id());
 334     syncer::StringOrdinal extension3_app_launch =
 335         extension_sorting->GetAppLaunchOrdinal(extension3()->id());
 336
 337     // The overlapping extensions should have be adjusted so that they are
 338     // sorted by their id.
 339     EXPECT_EQ(extension1()->id() < extension2()->id(),
 340               extension1_app_launch.LessThan(extension2_app_launch));
 341     EXPECT_EQ(extension1()->id() < extension3()->id(),
 342               extension1_app_launch.LessThan(extension3_app_launch));
 343     EXPECT_EQ(extension2()->id() < extension3()->id(),
 344               extension2_app_launch.LessThan(extension3_app_launch));
 345
 346     // The page ordinal should be unchanged.
 347     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension1()->id()).Equals(
 348         repeated_ordinal_));
 349     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension2()->id()).Equals(
 350         repeated_ordinal_));
 351     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension3()->id()).Equals(
 352         repeated_ordinal_));
 353   }
 354
 355  private:
 356   syncer::StringOrdinal repeated_ordinal_;
 357 };
 358 TEST_F(ExtensionSortingFixNTPCollisionsAllCollide,
 359        ExtensionSortingFixNTPCollisionsAllCollide) {}
 360
 361 class ExtensionSortingFixNTPCollisionsSomeCollideAtStart
 362     : public extensions::PrefsPrepopulatedTestBase {
 363  public:
 364   ExtensionSortingFixNTPCollisionsSomeCollideAtStart() {}
 365   virtual ~ExtensionSortingFixNTPCollisionsSomeCollideAtStart() {}
 366
 367   virtual void Initialize() OVERRIDE {
 368     first_ordinal_ = syncer::StringOrdinal::CreateInitialOrdinal();
 369     syncer::StringOrdinal second_ordinal = first_ordinal_.CreateAfter();
 370
 371     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 372
 373     // Have the first two extension in the same position, with a third
 374     // (non-colliding) extension after.
 375
 376     extension_sorting->SetAppLaunchOrdinal(extension1()->id(), first_ordinal_);
 377     extension_sorting->SetPageOrdinal(extension1()->id(), first_ordinal_);
 378
 379     extension_sorting->SetAppLaunchOrdinal(extension2()->id(), first_ordinal_);
 380     extension_sorting->SetPageOrdinal(extension2()->id(), first_ordinal_);
 381
 382     extension_sorting->SetAppLaunchOrdinal(extension3()->id(), second_ordinal);
 383     extension_sorting->SetPageOrdinal(extension3()->id(), first_ordinal_);
 384
 385     extension_sorting->FixNTPOrdinalCollisions();
 386   }
 387   virtual void Verify() OVERRIDE {
 388     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 389     syncer::StringOrdinal extension1_app_launch =
 390         extension_sorting->GetAppLaunchOrdinal(extension1()->id());
 391     syncer::StringOrdinal extension2_app_launch =
 392         extension_sorting->GetAppLaunchOrdinal(extension2()->id());
 393     syncer::StringOrdinal extension3_app_launch =
 394         extension_sorting->GetAppLaunchOrdinal(extension3()->id());
 395
 396     // The overlapping extensions should have be adjusted so that they are
 397     // sorted by their id, but they both should be before ext3, which wasn't
 398     // overlapping.
 399     EXPECT_EQ(extension1()->id() < extension2()->id(),
 400               extension1_app_launch.LessThan(extension2_app_launch));
 401     EXPECT_TRUE(extension1_app_launch.LessThan(extension3_app_launch));
 402     EXPECT_TRUE(extension2_app_launch.LessThan(extension3_app_launch));
 403
 404     // The page ordinal should be unchanged.
 405     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension1()->id()).Equals(
 406         first_ordinal_));
 407     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension2()->id()).Equals(
 408         first_ordinal_));
 409     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension3()->id()).Equals(
 410         first_ordinal_));
 411   }
 412
 413  private:
 414   syncer::StringOrdinal first_ordinal_;
 415 };
 416 TEST_F(ExtensionSortingFixNTPCollisionsSomeCollideAtStart,
 417        ExtensionSortingFixNTPCollisionsSomeCollideAtStart) {}
 418
 419 class ExtensionSortingFixNTPCollisionsSomeCollideAtEnd
 420     : public extensions::PrefsPrepopulatedTestBase {
 421  public:
 422   ExtensionSortingFixNTPCollisionsSomeCollideAtEnd() {}
 423   virtual ~ExtensionSortingFixNTPCollisionsSomeCollideAtEnd() {}
 424
 425   virtual void Initialize() OVERRIDE {
 426     first_ordinal_ = syncer::StringOrdinal::CreateInitialOrdinal();
 427     syncer::StringOrdinal second_ordinal = first_ordinal_.CreateAfter();
 428
 429     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 430
 431     // Have the first extension in a non-colliding position, followed by two
 432     // two extension in the same position.
 433
 434     extension_sorting->SetAppLaunchOrdinal(extension1()->id(), first_ordinal_);
 435     extension_sorting->SetPageOrdinal(extension1()->id(), first_ordinal_);
 436
 437     extension_sorting->SetAppLaunchOrdinal(extension2()->id(), second_ordinal);
 438     extension_sorting->SetPageOrdinal(extension2()->id(), first_ordinal_);
 439
 440     extension_sorting->SetAppLaunchOrdinal(extension3()->id(), second_ordinal);
 441     extension_sorting->SetPageOrdinal(extension3()->id(), first_ordinal_);
 442
 443     extension_sorting->FixNTPOrdinalCollisions();
 444   }
 445   virtual void Verify() OVERRIDE {
 446     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 447     syncer::StringOrdinal extension1_app_launch =
 448         extension_sorting->GetAppLaunchOrdinal(extension1()->id());
 449     syncer::StringOrdinal extension2_app_launch =
 450         extension_sorting->GetAppLaunchOrdinal(extension2()->id());
 451     syncer::StringOrdinal extension3_app_launch =
 452         extension_sorting->GetAppLaunchOrdinal(extension3()->id());
 453
 454     // The overlapping extensions should have be adjusted so that they are
 455     // sorted by their id, but they both should be after ext1, which wasn't
 456     // overlapping.
 457     EXPECT_TRUE(extension1_app_launch.LessThan(extension2_app_launch));
 458     EXPECT_TRUE(extension1_app_launch.LessThan(extension3_app_launch));
 459     EXPECT_EQ(extension2()->id() < extension3()->id(),
 460               extension2_app_launch.LessThan(extension3_app_launch));
 461
 462     // The page ordinal should be unchanged.
 463     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension1()->id()).Equals(
 464         first_ordinal_));
 465     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension2()->id()).Equals(
 466         first_ordinal_));
 467     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension3()->id()).Equals(
 468         first_ordinal_));
 469   }
 470
 471  private:
 472   syncer::StringOrdinal first_ordinal_;
 473 };
 474 TEST_F(ExtensionSortingFixNTPCollisionsSomeCollideAtEnd,
 475        ExtensionSortingFixNTPCollisionsSomeCollideAtEnd) {}
 476
 477 class ExtensionSortingFixNTPCollisionsTwoCollisions
 478     : public extensions::PrefsPrepopulatedTestBase {
 479  public:
 480   ExtensionSortingFixNTPCollisionsTwoCollisions() {}
 481   virtual ~ExtensionSortingFixNTPCollisionsTwoCollisions() {}
 482
 483   virtual void Initialize() OVERRIDE {
 484     first_ordinal_ = syncer::StringOrdinal::CreateInitialOrdinal();
 485     syncer::StringOrdinal second_ordinal = first_ordinal_.CreateAfter();
 486
 487     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 488
 489     // Have two extensions colliding, followed by two more colliding extensions.
 490     extension_sorting->SetAppLaunchOrdinal(extension1()->id(), first_ordinal_);
 491     extension_sorting->SetPageOrdinal(extension1()->id(), first_ordinal_);
 492
 493     extension_sorting->SetAppLaunchOrdinal(extension2()->id(), first_ordinal_);
 494     extension_sorting->SetPageOrdinal(extension2()->id(), first_ordinal_);
 495
 496     extension_sorting->SetAppLaunchOrdinal(extension3()->id(), second_ordinal);
 497     extension_sorting->SetPageOrdinal(extension3()->id(), first_ordinal_);
 498
 499     extension_sorting->SetAppLaunchOrdinal(extension4()->id(), second_ordinal);
 500     extension_sorting->SetPageOrdinal(extension4()->id(), first_ordinal_);
 501
 502     extension_sorting->FixNTPOrdinalCollisions();
 503   }
 504   virtual void Verify() OVERRIDE {
 505     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 506     syncer::StringOrdinal extension1_app_launch =
 507         extension_sorting->GetAppLaunchOrdinal(extension1()->id());
 508     syncer::StringOrdinal extension2_app_launch =
 509         extension_sorting->GetAppLaunchOrdinal(extension2()->id());
 510     syncer::StringOrdinal extension3_app_launch =
 511         extension_sorting->GetAppLaunchOrdinal(extension3()->id());
 512     syncer::StringOrdinal extension4_app_launch =
 513         extension_sorting->GetAppLaunchOrdinal(extension4()->id());
 514
 515     // The overlapping extensions should have be adjusted so that they are
 516     // sorted by their id, with |ext1| and |ext2| appearing before |ext3| and
 517     // |ext4|.
 518     EXPECT_TRUE(extension1_app_launch.LessThan(extension3_app_launch));
 519     EXPECT_TRUE(extension1_app_launch.LessThan(extension4_app_launch));
 520     EXPECT_TRUE(extension2_app_launch.LessThan(extension3_app_launch));
 521     EXPECT_TRUE(extension2_app_launch.LessThan(extension4_app_launch));
 522
 523     EXPECT_EQ(extension1()->id() < extension2()->id(),
 524               extension1_app_launch.LessThan(extension2_app_launch));
 525     EXPECT_EQ(extension3()->id() < extension4()->id(),
 526               extension3_app_launch.LessThan(extension4_app_launch));
 527
 528     // The page ordinal should be unchanged.
 529     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension1()->id()).Equals(
 530         first_ordinal_));
 531     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension2()->id()).Equals(
 532         first_ordinal_));
 533     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension3()->id()).Equals(
 534         first_ordinal_));
 535     EXPECT_TRUE(extension_sorting->GetPageOrdinal(extension4()->id()).Equals(
 536         first_ordinal_));
 537   }
 538
 539  private:
 540   syncer::StringOrdinal first_ordinal_;
 541 };
 542 TEST_F(ExtensionSortingFixNTPCollisionsTwoCollisions,
 543        ExtensionSortingFixNTPCollisionsTwoCollisions) {}
 544
 545 class ExtensionSortingEnsureValidOrdinals
 546     : public extensions::PrefsPrepopulatedTestBase {
 547  public :
 548   ExtensionSortingEnsureValidOrdinals() {}
 549   virtual ~ExtensionSortingEnsureValidOrdinals() {}
 550
 551   virtual void Initialize() OVERRIDE {}
 552   virtual void Verify() OVERRIDE {
 553     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 554
 555     // Give ext1 invalid ordinals and then check that EnsureValidOrdinals fixes
 556     // them.
 557     extension_sorting->SetAppLaunchOrdinal(extension1()->id(),
 558                                            syncer::StringOrdinal());
 559     extension_sorting->SetPageOrdinal(extension1()->id(),
 560                                       syncer::StringOrdinal());
 561
 562     extension_sorting->EnsureValidOrdinals(extension1()->id(),
 563                                            syncer::StringOrdinal());
 564
 565     EXPECT_TRUE(
 566         extension_sorting->GetAppLaunchOrdinal(extension1()->id()).IsValid());
 567     EXPECT_TRUE(
 568         extension_sorting->GetPageOrdinal(extension1()->id()).IsValid());
 569   }
 570 };
 571 TEST_F(ExtensionSortingEnsureValidOrdinals,
 572        ExtensionSortingEnsureValidOrdinals) {}
 573
 574 class ExtensionSortingPageOrdinalMapping
 575     : public extensions::PrefsPrepopulatedTestBase {
 576  public:
 577   ExtensionSortingPageOrdinalMapping() {}
 578   virtual ~ExtensionSortingPageOrdinalMapping() {}
 579
 580   virtual void Initialize() OVERRIDE {}
 581   virtual void Verify() OVERRIDE {
 582     std::string ext_1 = "ext_1";
 583     std::string ext_2 = "ext_2";
 584
 585     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 586     syncer::StringOrdinal first_ordinal =
 587         syncer::StringOrdinal::CreateInitialOrdinal();
 588
 589     // Ensure attempting to removing a mapping with an invalid page doesn't
 590     // modify the map.
 591     EXPECT_TRUE(extension_sorting->ntp_ordinal_map_.empty());
 592     extension_sorting->RemoveOrdinalMapping(
 593         ext_1, first_ordinal, first_ordinal);
 594     EXPECT_TRUE(extension_sorting->ntp_ordinal_map_.empty());
 595
 596     // Add new mappings.
 597     extension_sorting->AddOrdinalMapping(ext_1, first_ordinal, first_ordinal);
 598     extension_sorting->AddOrdinalMapping(ext_2, first_ordinal, first_ordinal);
 599
 600     EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_.size());
 601     EXPECT_EQ(2U, extension_sorting->ntp_ordinal_map_[first_ordinal].size());
 602
 603     ExtensionSorting::AppLaunchOrdinalMap::iterator it =
 604         extension_sorting->ntp_ordinal_map_[first_ordinal].find(first_ordinal);
 605     EXPECT_EQ(ext_1, it->second);
 606     ++it;
 607     EXPECT_EQ(ext_2, it->second);
 608
 609     extension_sorting->RemoveOrdinalMapping(ext_1,
 610                                             first_ordinal,
 611                                             first_ordinal);
 612     EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_.size());
 613     EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_[first_ordinal].size());
 614
 615     it = extension_sorting->ntp_ordinal_map_[first_ordinal].find(
 616         first_ordinal);
 617     EXPECT_EQ(ext_2, it->second);
 618
 619     // Ensure that attempting to remove an extension with a valid page and app
 620     // launch ordinals, but a unused id has no effect.
 621     extension_sorting->RemoveOrdinalMapping(
 622         "invalid_ext", first_ordinal, first_ordinal);
 623     EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_.size());
 624     EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_[first_ordinal].size());
 625
 626     it = extension_sorting->ntp_ordinal_map_[first_ordinal].find(
 627         first_ordinal);
 628     EXPECT_EQ(ext_2, it->second);
 629   }
 630 };
 631 TEST_F(ExtensionSortingPageOrdinalMapping,
 632        ExtensionSortingPageOrdinalMapping) {}
 633
 634 class ExtensionSortingPreinstalledAppsBase
 635     : public extensions::PrefsPrepopulatedTestBase {
 636  public:
 637   ExtensionSortingPreinstalledAppsBase() {
 638     DictionaryValue simple_dict;
 639     simple_dict.SetString(keys::kVersion, "1.0.0.0");
 640     simple_dict.SetString(keys::kName, "unused");
 641     simple_dict.SetString(keys::kApp, "true");
 642     simple_dict.SetString(keys::kLaunchLocalPath, "fake.html");
 643
 644     std::string error;
 645     app1_scoped_ = Extension::Create(
 646         prefs_.temp_dir().AppendASCII("app1_"), Manifest::EXTERNAL_PREF,
 647         simple_dict, Extension::NO_FLAGS, &error);
 648     prefs()->OnExtensionInstalled(app1_scoped_.get(),
 649                                   Extension::ENABLED,
 650                                   Blacklist::NOT_BLACKLISTED,
 651                                   syncer::StringOrdinal());
 652
 653     app2_scoped_ = Extension::Create(
 654         prefs_.temp_dir().AppendASCII("app2_"), Manifest::EXTERNAL_PREF,
 655         simple_dict, Extension::NO_FLAGS, &error);
 656     prefs()->OnExtensionInstalled(app2_scoped_.get(),
 657                                   Extension::ENABLED,
 658                                   Blacklist::NOT_BLACKLISTED,
 659                                   syncer::StringOrdinal());
 660
 661     app1_ = app1_scoped_.get();
 662     app2_ = app2_scoped_.get();
 663   }
 664   virtual ~ExtensionSortingPreinstalledAppsBase() {}
 665
 666  protected:
 667   // Weak references, for convenience.
 668   Extension* app1_;
 669   Extension* app2_;
 670
 671  private:
 672   scoped_refptr<Extension> app1_scoped_;
 673   scoped_refptr<Extension> app2_scoped_;
 674 };
 675
 676 class ExtensionSortingGetMinOrMaxAppLaunchOrdinalsOnPage
 677     : public ExtensionSortingPreinstalledAppsBase {
 678  public:
 679   ExtensionSortingGetMinOrMaxAppLaunchOrdinalsOnPage() {}
 680   virtual ~ExtensionSortingGetMinOrMaxAppLaunchOrdinalsOnPage() {}
 681
 682   virtual void Initialize() OVERRIDE {}
 683   virtual void Verify() OVERRIDE {
 684     syncer::StringOrdinal page = syncer::StringOrdinal::CreateInitialOrdinal();
 685     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 686
 687     syncer::StringOrdinal min =
 688         extension_sorting->GetMinOrMaxAppLaunchOrdinalsOnPage(
 689             page,
 690             ExtensionSorting::MIN_ORDINAL);
 691     syncer::StringOrdinal max =
 692         extension_sorting->GetMinOrMaxAppLaunchOrdinalsOnPage(
 693             page,
 694             ExtensionSorting::MAX_ORDINAL);
 695     EXPECT_TRUE(min.IsValid());
 696     EXPECT_TRUE(max.IsValid());
 697     EXPECT_TRUE(min.LessThan(max));
 698
 699     // Ensure that the min and max values aren't set for empty pages.
 700     min = syncer::StringOrdinal();
 701     max = syncer::StringOrdinal();
 702     syncer::StringOrdinal empty_page = page.CreateAfter();
 703     EXPECT_FALSE(min.IsValid());
 704     EXPECT_FALSE(max.IsValid());
 705     min = extension_sorting->GetMinOrMaxAppLaunchOrdinalsOnPage(
 706         empty_page,
 707         ExtensionSorting::MIN_ORDINAL);
 708     max = extension_sorting->GetMinOrMaxAppLaunchOrdinalsOnPage(
 709         empty_page,
 710         ExtensionSorting::MAX_ORDINAL);
 711     EXPECT_FALSE(min.IsValid());
 712     EXPECT_FALSE(max.IsValid());
 713   }
 714 };
 715 TEST_F(ExtensionSortingGetMinOrMaxAppLaunchOrdinalsOnPage,
 716        ExtensionSortingGetMinOrMaxAppLaunchOrdinalsOnPage) {}
 717
 718 // Make sure that empty pages aren't removed from the integer to ordinal
 719 // mapping. See http://crbug.com/109802 for details.
 720 class ExtensionSortingKeepEmptyStringOrdinalPages
 721     : public ExtensionSortingPreinstalledAppsBase {
 722  public:
 723   ExtensionSortingKeepEmptyStringOrdinalPages() {}
 724   virtual ~ExtensionSortingKeepEmptyStringOrdinalPages() {}
 725
 726   virtual void Initialize() OVERRIDE {
 727     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 728
 729     syncer::StringOrdinal first_page =
 730         syncer::StringOrdinal::CreateInitialOrdinal();
 731     extension_sorting->SetPageOrdinal(app1_->id(), first_page);
 732     EXPECT_EQ(0, extension_sorting->PageStringOrdinalAsInteger(first_page));
 733
 734     last_page_ = first_page.CreateAfter();
 735     extension_sorting->SetPageOrdinal(app2_->id(), last_page_);
 736     EXPECT_EQ(1, extension_sorting->PageStringOrdinalAsInteger(last_page_));
 737
 738     // Move the second app to create an empty page.
 739     extension_sorting->SetPageOrdinal(app2_->id(), first_page);
 740     EXPECT_EQ(0, extension_sorting->PageStringOrdinalAsInteger(first_page));
 741   }
 742   virtual void Verify() OVERRIDE {
 743     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 744
 745     // Move the second app to a new empty page at the end, skipping over
 746     // the current empty page.
 747     last_page_ = last_page_.CreateAfter();
 748     extension_sorting->SetPageOrdinal(app2_->id(), last_page_);
 749     EXPECT_EQ(2, extension_sorting->PageStringOrdinalAsInteger(last_page_));
 750     EXPECT_TRUE(
 751         last_page_.Equals(extension_sorting->PageIntegerAsStringOrdinal(2)));
 752   }
 753
 754  private:
 755   syncer::StringOrdinal last_page_;
 756 };
 757 TEST_F(ExtensionSortingKeepEmptyStringOrdinalPages,
 758        ExtensionSortingKeepEmptyStringOrdinalPages) {}
 759
 760 class ExtensionSortingMakesFillerOrdinals
 761     : public ExtensionSortingPreinstalledAppsBase {
 762  public:
 763   ExtensionSortingMakesFillerOrdinals() {}
 764   virtual ~ExtensionSortingMakesFillerOrdinals() {}
 765
 766   virtual void Initialize() OVERRIDE {
 767     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 768
 769     syncer::StringOrdinal first_page =
 770         syncer::StringOrdinal::CreateInitialOrdinal();
 771     extension_sorting->SetPageOrdinal(app1_->id(), first_page);
 772     EXPECT_EQ(0, extension_sorting->PageStringOrdinalAsInteger(first_page));
 773   }
 774   virtual void Verify() OVERRIDE {
 775     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 776
 777     // Because the UI can add an unlimited number of empty pages without an app
 778     // on them, this test simulates dropping of an app on the 1st and 4th empty
 779     // pages (3rd and 6th pages by index) to ensure we don't crash and that
 780     // filler ordinals are created as needed. See: http://crbug.com/122214
 781     syncer::StringOrdinal page_three =
 782         extension_sorting->PageIntegerAsStringOrdinal(2);
 783     extension_sorting->SetPageOrdinal(app1_->id(), page_three);
 784     EXPECT_EQ(2, extension_sorting->PageStringOrdinalAsInteger(page_three));
 785
 786     syncer::StringOrdinal page_six =
 787         extension_sorting->PageIntegerAsStringOrdinal(5);
 788     extension_sorting->SetPageOrdinal(app1_->id(), page_six);
 789     EXPECT_EQ(5, extension_sorting->PageStringOrdinalAsInteger(page_six));
 790   }
 791 };
 792 TEST_F(ExtensionSortingMakesFillerOrdinals,
 793        ExtensionSortingMakesFillerOrdinals) {}
 794
 795 class ExtensionSortingDefaultOrdinalsBase : public ExtensionSortingTest {
 796  public:
 797   ExtensionSortingDefaultOrdinalsBase() {}
 798   virtual ~ExtensionSortingDefaultOrdinalsBase() {}
 799
 800   virtual void Initialize() OVERRIDE {
 801     app_ = CreateApp("app");
 802
 803     InitDefaultOrdinals();
 804     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 805     ExtensionSorting::AppOrdinalsMap& sorting_defaults =
 806         extension_sorting->default_ordinals_;
 807     sorting_defaults[app_->id()].page_ordinal = default_page_ordinal_;
 808     sorting_defaults[app_->id()].app_launch_ordinal =
 809         default_app_launch_ordinal_;
 810
 811     SetupUserOrdinals();
 812     InstallApps();
 813   }
 814
 815  protected:
 816   scoped_refptr<Extension> CreateApp(const std::string& name) {
 817     DictionaryValue simple_dict;
 818     simple_dict.SetString(keys::kVersion, "1.0.0.0");
 819     simple_dict.SetString(keys::kName, name);
 820     simple_dict.SetString(keys::kApp, "true");
 821     simple_dict.SetString(keys::kLaunchLocalPath, "fake.html");
 822
 823     std::string errors;
 824     scoped_refptr<Extension> app = Extension::Create(
 825         prefs_.temp_dir().AppendASCII(name), Manifest::EXTERNAL_PREF,
 826         simple_dict, Extension::NO_FLAGS, &errors);
 827     EXPECT_TRUE(app.get()) << errors;
 828     EXPECT_TRUE(Extension::IdIsValid(app->id()));
 829     return app;
 830   }
 831
 832   void InitDefaultOrdinals() {
 833     default_page_ordinal_ =
 834         syncer::StringOrdinal::CreateInitialOrdinal().CreateAfter();
 835     default_app_launch_ordinal_ =
 836         syncer::StringOrdinal::CreateInitialOrdinal().CreateBefore();
 837   }
 838
 839   virtual void SetupUserOrdinals() {}
 840
 841   virtual void InstallApps() {
 842     prefs()->OnExtensionInstalled(app_.get(),
 843                                   Extension::ENABLED,
 844                                   Blacklist::NOT_BLACKLISTED,
 845                                   syncer::StringOrdinal());
 846   }
 847
 848   scoped_refptr<Extension> app_;
 849   syncer::StringOrdinal default_page_ordinal_;
 850   syncer::StringOrdinal default_app_launch_ordinal_;
 851 };
 852
 853 // Tests that the app gets its default ordinals.
 854 class ExtensionSortingDefaultOrdinals
 855     : public ExtensionSortingDefaultOrdinalsBase {
 856  public:
 857   ExtensionSortingDefaultOrdinals() {}
 858   virtual ~ExtensionSortingDefaultOrdinals() {}
 859
 860   virtual void Verify() OVERRIDE {
 861     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 862     EXPECT_TRUE(extension_sorting->GetPageOrdinal(app_->id()).Equals(
 863         default_page_ordinal_));
 864     EXPECT_TRUE(extension_sorting->GetAppLaunchOrdinal(app_->id()).Equals(
 865         default_app_launch_ordinal_));
 866   }
 867 };
 868 TEST_F(ExtensionSortingDefaultOrdinals,
 869        ExtensionSortingDefaultOrdinals) {}
 870
 871 // Tests that the default page ordinal is overridden by install page ordinal.
 872 class ExtensionSortingDefaultOrdinalOverriddenByInstallPage
 873     : public ExtensionSortingDefaultOrdinalsBase {
 874  public:
 875   ExtensionSortingDefaultOrdinalOverriddenByInstallPage() {}
 876   virtual ~ExtensionSortingDefaultOrdinalOverriddenByInstallPage() {}
 877
 878   virtual void Verify() OVERRIDE {
 879     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 880
 881     EXPECT_FALSE(extension_sorting->GetPageOrdinal(app_->id()).Equals(
 882         default_page_ordinal_));
 883     EXPECT_TRUE(extension_sorting->GetPageOrdinal(app_->id()).Equals(
 884         install_page_));
 885   }
 886
 887  protected:
 888   virtual void InstallApps() OVERRIDE {
 889     install_page_ = default_page_ordinal_.CreateAfter();
 890     prefs()->OnExtensionInstalled(app_.get(),
 891                                   Extension::ENABLED,
 892                                   Blacklist::NOT_BLACKLISTED,
 893                                   install_page_);
 894   }
 895
 896  private:
 897   syncer::StringOrdinal install_page_;
 898 };
 899 TEST_F(ExtensionSortingDefaultOrdinalOverriddenByInstallPage,
 900        ExtensionSortingDefaultOrdinalOverriddenByInstallPage) {}
 901
 902 // Tests that the default ordinals are overridden by user values.
 903 class ExtensionSortingDefaultOrdinalOverriddenByUserValue
 904     : public ExtensionSortingDefaultOrdinalsBase {
 905  public:
 906   ExtensionSortingDefaultOrdinalOverriddenByUserValue() {}
 907   virtual ~ExtensionSortingDefaultOrdinalOverriddenByUserValue() {}
 908
 909   virtual void Verify() OVERRIDE {
 910     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 911
 912     EXPECT_TRUE(extension_sorting->GetPageOrdinal(app_->id()).Equals(
 913         user_page_ordinal_));
 914     EXPECT_TRUE(extension_sorting->GetAppLaunchOrdinal(app_->id()).Equals(
 915         user_app_launch_ordinal_));
 916   }
 917
 918  protected:
 919   virtual void SetupUserOrdinals() OVERRIDE {
 920     user_page_ordinal_ = default_page_ordinal_.CreateAfter();
 921     user_app_launch_ordinal_ = default_app_launch_ordinal_.CreateBefore();
 922
 923     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 924     extension_sorting->SetPageOrdinal(app_->id(), user_page_ordinal_);
 925     extension_sorting->SetAppLaunchOrdinal(app_->id(),
 926                                            user_app_launch_ordinal_);
 927   }
 928
 929  private:
 930   syncer::StringOrdinal user_page_ordinal_;
 931   syncer::StringOrdinal user_app_launch_ordinal_;
 932 };
 933 TEST_F(ExtensionSortingDefaultOrdinalOverriddenByUserValue,
 934        ExtensionSortingDefaultOrdinalOverriddenByUserValue) {}
 935
 936 // Tests that the default app launch ordinal is changed to avoid collision.
 937 class ExtensionSortingDefaultOrdinalNoCollision
 938     : public ExtensionSortingDefaultOrdinalsBase {
 939  public:
 940   ExtensionSortingDefaultOrdinalNoCollision() {}
 941   virtual ~ExtensionSortingDefaultOrdinalNoCollision() {}
 942
 943   virtual void Verify() OVERRIDE {
 944     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 945
 946     // Use the default page.
 947     EXPECT_TRUE(extension_sorting->GetPageOrdinal(app_->id()).Equals(
 948         default_page_ordinal_));
 949     // Not using the default app launch ordinal because of the collision.
 950     EXPECT_FALSE(extension_sorting->GetAppLaunchOrdinal(app_->id()).Equals(
 951         default_app_launch_ordinal_));
 952   }
 953
 954  protected:
 955   virtual void SetupUserOrdinals() OVERRIDE {
 956     other_app_ = prefs_.AddApp("other_app");
 957     // Creates a collision.
 958     ExtensionSorting* extension_sorting = prefs()->extension_sorting();
 959     extension_sorting->SetPageOrdinal(other_app_->id(), default_page_ordinal_);
 960     extension_sorting->SetAppLaunchOrdinal(other_app_->id(),
 961                                            default_app_launch_ordinal_);
 962
 963     yet_another_app_ = prefs_.AddApp("yet_aother_app");
 964     extension_sorting->SetPageOrdinal(yet_another_app_->id(),
 965                                       default_page_ordinal_);
 966     extension_sorting->SetAppLaunchOrdinal(yet_another_app_->id(),
 967                                            default_app_launch_ordinal_);
 968   }
 969
 970  private:
 971   scoped_refptr<Extension> other_app_;
 972   scoped_refptr<Extension> yet_another_app_;
 973 };
 974 TEST_F(ExtensionSortingDefaultOrdinalNoCollision,
 975        ExtensionSortingDefaultOrdinalNoCollision) {}