LCOV - code coverage report
Current view: top level - test/cctest - test-dictionary.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 110 110 100.0 %
Date: 2019-01-20 Functions: 10 10 100.0 %

          Line data    Source code
       1             : // Copyright 2011 the V8 project authors. All rights reserved.
       2             : // Redistribution and use in source and binary forms, with or without
       3             : // modification, are permitted provided that the following conditions are
       4             : // met:
       5             : //
       6             : //     * Redistributions of source code must retain the above copyright
       7             : //       notice, this list of conditions and the following disclaimer.
       8             : //     * Redistributions in binary form must reproduce the above
       9             : //       copyright notice, this list of conditions and the following
      10             : //       disclaimer in the documentation and/or other materials provided
      11             : //       with the distribution.
      12             : //     * Neither the name of Google Inc. nor the names of its
      13             : //       contributors may be used to endorse or promote products derived
      14             : //       from this software without specific prior written permission.
      15             : //
      16             : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
      17             : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
      18             : // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
      19             : // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
      20             : // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
      21             : // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
      22             : // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
      23             : // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
      24             : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
      25             : // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
      26             : // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
      27             : 
      28             : #include "src/v8.h"
      29             : #include "test/cctest/cctest.h"
      30             : 
      31             : #include "src/builtins/builtins-constructor.h"
      32             : #include "src/debug/debug.h"
      33             : #include "src/execution.h"
      34             : #include "src/global-handles.h"
      35             : #include "src/heap/factory.h"
      36             : #include "src/heap/spaces.h"
      37             : #include "src/objects-inl.h"
      38             : #include "src/objects/hash-table-inl.h"
      39             : #include "test/cctest/heap/heap-utils.h"
      40             : 
      41             : namespace v8 {
      42             : namespace internal {
      43             : 
      44             : namespace {
      45             : 
      46             : 
      47             : template<typename HashMap>
      48           5 : static void TestHashMap(Handle<HashMap> table) {
      49             :   Isolate* isolate = CcTest::i_isolate();
      50             :   Factory* factory = isolate->factory();
      51             : 
      52           5 :   Handle<JSObject> a = factory->NewJSArray(7);
      53           5 :   Handle<JSObject> b = factory->NewJSArray(11);
      54           5 :   table = HashMap::Put(table, a, b);
      55           5 :   CHECK_EQ(1, table->NumberOfElements());
      56          15 :   CHECK_EQ(table->Lookup(a), *b);
      57             :   // When the key does not exist in the map, Lookup returns the hole.
      58           5 :   ReadOnlyRoots roots(CcTest::heap());
      59          15 :   CHECK_EQ(table->Lookup(b), roots.the_hole_value());
      60             : 
      61             :   // Keys still have to be valid after objects were moved.
      62           5 :   CcTest::CollectGarbage(NEW_SPACE);
      63           5 :   CHECK_EQ(1, table->NumberOfElements());
      64          15 :   CHECK_EQ(table->Lookup(a), *b);
      65          15 :   CHECK_EQ(table->Lookup(b), roots.the_hole_value());
      66             : 
      67             :   // Keys that are overwritten should not change number of elements.
      68          10 :   table = HashMap::Put(table, a, factory->NewJSArray(13));
      69           5 :   CHECK_EQ(1, table->NumberOfElements());
      70          15 :   CHECK_NE(table->Lookup(a), *b);
      71             : 
      72             :   // Keys that have been removed are mapped to the hole.
      73           5 :   bool was_present = false;
      74           5 :   table = HashMap::Remove(isolate, table, a, &was_present);
      75           5 :   CHECK(was_present);
      76           5 :   CHECK_EQ(0, table->NumberOfElements());
      77          15 :   CHECK_EQ(table->Lookup(a), roots.the_hole_value());
      78             : 
      79             :   // Keys should map back to their respective values and also should get
      80             :   // an identity hash code generated.
      81         505 :   for (int i = 0; i < 100; i++) {
      82         500 :     Handle<JSReceiver> key = factory->NewJSArray(7);
      83         500 :     Handle<JSObject> value = factory->NewJSArray(11);
      84         500 :     table = HashMap::Put(table, key, value);
      85        1000 :     CHECK_EQ(table->NumberOfElements(), i + 1);
      86         500 :     CHECK_NE(table->FindEntry(isolate, key), HashMap::kNotFound);
      87        1500 :     CHECK_EQ(table->Lookup(key), *value);
      88        1000 :     CHECK(key->GetIdentityHash()->IsSmi());
      89             :   }
      90             : 
      91             :   // Keys never added to the map which already have an identity hash
      92             :   // code should not be found.
      93         500 :   for (int i = 0; i < 100; i++) {
      94         500 :     Handle<JSReceiver> key = factory->NewJSArray(7);
      95        1000 :     CHECK(key->GetOrCreateIdentityHash(isolate)->IsSmi());
      96         500 :     CHECK_EQ(table->FindEntry(isolate, key), HashMap::kNotFound);
      97        1500 :     CHECK_EQ(table->Lookup(key), roots.the_hole_value());
      98        1000 :     CHECK(key->GetIdentityHash()->IsSmi());
      99             :   }
     100             : 
     101             :   // Keys that don't have an identity hash should not be found and also
     102             :   // should not get an identity hash code generated.
     103         500 :   for (int i = 0; i < 100; i++) {
     104         500 :     Handle<JSReceiver> key = factory->NewJSArray(7);
     105        1500 :     CHECK_EQ(table->Lookup(key), roots.the_hole_value());
     106         500 :     Object identity_hash = key->GetIdentityHash();
     107        1000 :     CHECK_EQ(roots.undefined_value(), identity_hash);
     108             :   }
     109           5 : }
     110             : 
     111             : 
     112       28342 : TEST(HashMap) {
     113           5 :   LocalContext context;
     114          10 :   v8::HandleScope scope(context->GetIsolate());
     115             :   Isolate* isolate = CcTest::i_isolate();
     116          10 :   TestHashMap(ObjectHashTable::New(isolate, 23));
     117           5 : }
     118             : 
     119             : template <typename HashSet>
     120           5 : static void TestHashSet(Handle<HashSet> table) {
     121             :   Isolate* isolate = CcTest::i_isolate();
     122             :   Factory* factory = isolate->factory();
     123             : 
     124           5 :   Handle<JSObject> a = factory->NewJSArray(7);
     125           5 :   Handle<JSObject> b = factory->NewJSArray(11);
     126           5 :   table = HashSet::Add(isolate, table, a);
     127           5 :   CHECK_EQ(1, table->NumberOfElements());
     128           5 :   CHECK(table->Has(isolate, a));
     129           5 :   CHECK(!table->Has(isolate, b));
     130             : 
     131             :   // Keys still have to be valid after objects were moved.
     132           5 :   CcTest::CollectGarbage(NEW_SPACE);
     133           5 :   CHECK_EQ(1, table->NumberOfElements());
     134           5 :   CHECK(table->Has(isolate, a));
     135           5 :   CHECK(!table->Has(isolate, b));
     136             : 
     137             :   // Keys that are overwritten should not change number of elements.
     138           5 :   table = HashSet::Add(isolate, table, a);
     139           5 :   CHECK_EQ(1, table->NumberOfElements());
     140           5 :   CHECK(table->Has(isolate, a));
     141           5 :   CHECK(!table->Has(isolate, b));
     142             : 
     143             :   // Keys that have been removed are mapped to the hole.
     144             :   // TODO(cbruni): not implemented yet.
     145             :   // bool was_present = false;
     146             :   // table = HashSet::Remove(table, a, &was_present);
     147             :   // CHECK(was_present);
     148             :   // CHECK_EQ(0, table->NumberOfElements());
     149             :   // CHECK(!table->Has(a));
     150             :   // CHECK(!table->Has(b));
     151             : 
     152             :   // Keys should map back to their respective values and also should get
     153             :   // an identity hash code generated.
     154         500 :   for (int i = 0; i < 100; i++) {
     155         500 :     Handle<JSReceiver> key = factory->NewJSArray(7);
     156         500 :     table = HashSet::Add(isolate, table, key);
     157        1000 :     CHECK_EQ(table->NumberOfElements(), i + 2);
     158         500 :     CHECK(table->Has(isolate, key));
     159        1000 :     CHECK(key->GetIdentityHash()->IsSmi());
     160             :   }
     161             : 
     162             :   // Keys never added to the map which already have an identity hash
     163             :   // code should not be found.
     164         500 :   for (int i = 0; i < 100; i++) {
     165         500 :     Handle<JSReceiver> key = factory->NewJSArray(7);
     166        1000 :     CHECK(key->GetOrCreateIdentityHash(isolate)->IsSmi());
     167         500 :     CHECK(!table->Has(isolate, key));
     168        1000 :     CHECK(key->GetIdentityHash()->IsSmi());
     169             :   }
     170             : 
     171             :   // Keys that don't have an identity hash should not be found and also
     172             :   // should not get an identity hash code generated.
     173         500 :   for (int i = 0; i < 100; i++) {
     174         500 :     Handle<JSReceiver> key = factory->NewJSArray(7);
     175         500 :     CHECK(!table->Has(isolate, key));
     176         500 :     Object identity_hash = key->GetIdentityHash();
     177        1500 :     CHECK_EQ(ReadOnlyRoots(CcTest::heap()).undefined_value(), identity_hash);
     178             :   }
     179           5 : }
     180             : 
     181       28342 : TEST(HashSet) {
     182           5 :   LocalContext context;
     183          10 :   v8::HandleScope scope(context->GetIsolate());
     184             :   Isolate* isolate = CcTest::i_isolate();
     185          10 :   TestHashSet(ObjectHashSet::New(isolate, 23));
     186           5 : }
     187             : 
     188             : class ObjectHashTableTest: public ObjectHashTable {
     189             :  public:
     190          10 :   explicit ObjectHashTableTest(ObjectHashTable o) : ObjectHashTable(o) {}
     191             :   ObjectHashTableTest* operator->() { return this; }
     192             : 
     193        1915 :   void insert(int entry, int key, int value) {
     194             :     set(EntryToIndex(entry), Smi::FromInt(key));
     195             :     set(EntryToIndex(entry) + 1, Smi::FromInt(value));
     196        1915 :   }
     197             : 
     198        1915 :   int lookup(int key) {
     199             :     Handle<Object> key_obj(Smi::FromInt(key), CcTest::i_isolate());
     200        1915 :     return Smi::ToInt(Lookup(key_obj));
     201             :   }
     202             : 
     203             :   int capacity() {
     204          10 :     return Capacity();
     205             :   }
     206             : };
     207             : 
     208             : 
     209       28342 : TEST(HashTableRehash) {
     210           5 :   LocalContext context;
     211             :   Isolate* isolate = CcTest::i_isolate();
     212          10 :   v8::HandleScope scope(context->GetIsolate());
     213             :   // Test almost filled table.
     214             :   {
     215           5 :     Handle<ObjectHashTable> table = ObjectHashTable::New(isolate, 100);
     216             :     ObjectHashTableTest t(*table);
     217             :     int capacity = t->capacity();
     218        1280 :     for (int i = 0; i < capacity - 1; i++) {
     219        1275 :       t->insert(i, i * i, i);
     220             :     }
     221           5 :     t->Rehash(isolate);
     222        1280 :     for (int i = 0; i < capacity - 1; i++) {
     223        1275 :       CHECK_EQ(i, t->lookup(i * i));
     224             :     }
     225             :   }
     226             :   // Test half-filled table.
     227             :   {
     228           5 :     Handle<ObjectHashTable> table = ObjectHashTable::New(isolate, 100);
     229             :     ObjectHashTableTest t(*table);
     230             :     int capacity = t->capacity();
     231         645 :     for (int i = 0; i < capacity / 2; i++) {
     232         640 :       t->insert(i, i * i, i);
     233             :     }
     234           5 :     t->Rehash(isolate);
     235         645 :     for (int i = 0; i < capacity / 2; i++) {
     236         640 :       CHECK_EQ(i, t->lookup(i * i));
     237             :     }
     238           5 :   }
     239           5 : }
     240             : 
     241             : 
     242             : #ifdef DEBUG
     243             : template<class HashSet>
     244             : static void TestHashSetCausesGC(Handle<HashSet> table) {
     245             :   Isolate* isolate = CcTest::i_isolate();
     246             :   Factory* factory = isolate->factory();
     247             : 
     248             :   Handle<JSObject> key = factory->NewJSArray(0);
     249             : 
     250             :   // Simulate a full heap so that generating an identity hash code
     251             :   // in subsequent calls will request GC.
     252             :   heap::SimulateFullSpace(CcTest::heap()->new_space());
     253             :   heap::SimulateFullSpace(CcTest::heap()->old_space());
     254             : 
     255             :   // Calling Contains() should not cause GC ever.
     256             :   int gc_count = isolate->heap()->gc_count();
     257             :   CHECK(!table->Contains(key));
     258             :   CHECK(gc_count == isolate->heap()->gc_count());
     259             : 
     260             :   // Calling Remove() will not cause GC in this case.
     261             :   bool was_present = false;
     262             :   table = HashSet::Remove(table, key, &was_present);
     263             :   CHECK(!was_present);
     264             :   CHECK(gc_count == isolate->heap()->gc_count());
     265             : 
     266             :   // Calling Add() should cause GC.
     267             :   table = HashSet::Add(table, key);
     268             :   CHECK(gc_count < isolate->heap()->gc_count());
     269             : }
     270             : #endif
     271             : 
     272             : 
     273             : #ifdef DEBUG
     274             : template <class HashMap>
     275             : static void TestHashMapDoesNotCauseGC(Handle<HashMap> table) {
     276             :   Isolate* isolate = CcTest::i_isolate();
     277             :   Factory* factory = isolate->factory();
     278             : 
     279             :   Handle<JSObject> key = factory->NewJSArray(0);
     280             : 
     281             :   // Even though we simulate a full heap, generating an identity hash
     282             :   // code in subsequent calls will not request GC.
     283             :   heap::SimulateFullSpace(CcTest::heap()->new_space());
     284             :   heap::SimulateFullSpace(CcTest::heap()->old_space());
     285             : 
     286             :   // Calling Lookup() should not cause GC ever.
     287             :   CHECK(table->Lookup(key)->IsTheHole(isolate));
     288             : 
     289             :   // Calling Put() should request GC by returning a failure.
     290             :   int gc_count = isolate->heap()->gc_count();
     291             :   HashMap::Put(table, key, key);
     292             :   CHECK(gc_count == isolate->heap()->gc_count());
     293             : }
     294             : 
     295             : 
     296             : TEST(ObjectHashTableCausesGC) {
     297             :   i::FLAG_stress_compaction = false;
     298             :   LocalContext context;
     299             :   v8::HandleScope scope(context->GetIsolate());
     300             :   Isolate* isolate = CcTest::i_isolate();
     301             :   TestHashMapDoesNotCauseGC(ObjectHashTable::New(isolate, 1));
     302             : }
     303             : #endif
     304             : 
     305       28342 : TEST(MaximumClonedShallowObjectProperties) {
     306             :   // Assert that a NameDictionary with kMaximumClonedShallowObjectProperties is
     307             :   // not in large-object space.
     308             :   const int max_capacity = NameDictionary::ComputeCapacity(
     309             :       ConstructorBuiltins::kMaximumClonedShallowObjectProperties);
     310           5 :   const int max_literal_entry = max_capacity / NameDictionary::kEntrySize;
     311             :   const int max_literal_index = NameDictionary::EntryToIndex(max_literal_entry);
     312           5 :   CHECK_LE(NameDictionary::OffsetOfElementAt(max_literal_index),
     313             :            kMaxRegularHeapObjectSize);
     314           5 : }
     315             : 
     316             : }  // namespace
     317             : 
     318             : }  // namespace internal
     319       85011 : }  // namespace v8

Generated by: LCOV version 1.10