src/3rdparty/v8/src/handles.cc

   1 // Copyright 2012 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 "v8.h"
  29
  30 #include "accessors.h"
  31 #include "api.h"
  32 #include "arguments.h"
  33 #include "bootstrapper.h"
  34 #include "compiler.h"
  35 #include "debug.h"
  36 #include "execution.h"
  37 #include "global-handles.h"
  38 #include "natives.h"
  39 #include "runtime.h"
  40 #include "string-search.h"
  41 #include "stub-cache.h"
  42 #include "vm-state-inl.h"
  43
  44 namespace v8 {
  45 namespace internal {
  46
  47
  48 int HandleScope::NumberOfHandles() {
  49   Isolate* isolate = Isolate::Current();
  50   HandleScopeImplementer* impl = isolate->handle_scope_implementer();
  51   int n = impl->blocks()->length();
  52   if (n == 0) return 0;
  53   return ((n - 1) * kHandleBlockSize) + static_cast<int>(
  54       (isolate->handle_scope_data()->next - impl->blocks()->last()));
  55 }
  56
  57
  58 Object** HandleScope::Extend() {
  59   Isolate* isolate = Isolate::Current();
  60   v8::ImplementationUtilities::HandleScopeData* current =
  61       isolate->handle_scope_data();
  62
  63   Object** result = current->next;
  64
  65   ASSERT(result == current->limit);
  66   // Make sure there's at least one scope on the stack and that the
  67   // top of the scope stack isn't a barrier.
  68   if (current->level == 0) {
  69     Utils::ReportApiFailure("v8::HandleScope::CreateHandle()",
  70                             "Cannot create a handle without a HandleScope");
  71     return NULL;
  72   }
  73   HandleScopeImplementer* impl = isolate->handle_scope_implementer();
  74   // If there's more room in the last block, we use that. This is used
  75   // for fast creation of scopes after scope barriers.
  76   if (!impl->blocks()->is_empty()) {
  77     Object** limit = &impl->blocks()->last()[kHandleBlockSize];
  78     if (current->limit != limit) {
  79       current->limit = limit;
  80       ASSERT(limit - current->next < kHandleBlockSize);
  81     }
  82   }
  83
  84   // If we still haven't found a slot for the handle, we extend the
  85   // current handle scope by allocating a new handle block.
  86   if (result == current->limit) {
  87     // If there's a spare block, use it for growing the current scope.
  88     result = impl->GetSpareOrNewBlock();
  89     // Add the extension to the global list of blocks, but count the
  90     // extension as part of the current scope.
  91     impl->blocks()->Add(result);
  92     current->limit = &result[kHandleBlockSize];
  93   }
  94
  95   return result;
  96 }
  97
  98
  99 void HandleScope::DeleteExtensions(Isolate* isolate) {
 100   ASSERT(isolate == Isolate::Current());
 101   v8::ImplementationUtilities::HandleScopeData* current =
 102       isolate->handle_scope_data();
 103   isolate->handle_scope_implementer()->DeleteExtensions(current->limit);
 104 }
 105
 106
 107 void HandleScope::ZapRange(Object** start, Object** end) {
 108   ASSERT(end - start <= kHandleBlockSize);
 109   for (Object** p = start; p != end; p++) {
 110     *reinterpret_cast<Address*>(p) = v8::internal::kHandleZapValue;
 111   }
 112 }
 113
 114
 115 Address HandleScope::current_level_address() {
 116   return reinterpret_cast<Address>(
 117       &Isolate::Current()->handle_scope_data()->level);
 118 }
 119
 120
 121 Address HandleScope::current_next_address() {
 122   return reinterpret_cast<Address>(
 123       &Isolate::Current()->handle_scope_data()->next);
 124 }
 125
 126
 127 Address HandleScope::current_limit_address() {
 128   return reinterpret_cast<Address>(
 129       &Isolate::Current()->handle_scope_data()->limit);
 130 }
 131
 132
 133 Handle<FixedArray> AddKeysFromJSArray(Handle<FixedArray> content,
 134                                       Handle<JSArray> array) {
 135   CALL_HEAP_FUNCTION(content->GetIsolate(),
 136                      content->AddKeysFromJSArray(*array), FixedArray);
 137 }
 138
 139
 140 Handle<FixedArray> UnionOfKeys(Handle<FixedArray> first,
 141                                Handle<FixedArray> second) {
 142   CALL_HEAP_FUNCTION(first->GetIsolate(),
 143                      first->UnionOfKeys(*second), FixedArray);
 144 }
 145
 146
 147 Handle<JSGlobalProxy> ReinitializeJSGlobalProxy(
 148     Handle<JSFunction> constructor,
 149     Handle<JSGlobalProxy> global) {
 150   CALL_HEAP_FUNCTION(
 151       constructor->GetIsolate(),
 152       constructor->GetHeap()->ReinitializeJSGlobalProxy(*constructor, *global),
 153       JSGlobalProxy);
 154 }
 155
 156
 157 void SetExpectedNofProperties(Handle<JSFunction> func, int nof) {
 158   // If objects constructed from this function exist then changing
 159   // 'estimated_nof_properties' is dangerous since the previous value might
 160   // have been compiled into the fast construct stub. More over, the inobject
 161   // slack tracking logic might have adjusted the previous value, so even
 162   // passing the same value is risky.
 163   if (func->shared()->live_objects_may_exist()) return;
 164
 165   func->shared()->set_expected_nof_properties(nof);
 166   if (func->has_initial_map()) {
 167     Handle<Map> new_initial_map =
 168         func->GetIsolate()->factory()->CopyMapDropTransitions(
 169             Handle<Map>(func->initial_map()));
 170     new_initial_map->set_unused_property_fields(nof);
 171     func->set_initial_map(*new_initial_map);
 172   }
 173 }
 174
 175
 176 void SetPrototypeProperty(Handle<JSFunction> func, Handle<JSObject> value) {
 177   CALL_HEAP_FUNCTION_VOID(func->GetIsolate(),
 178                           func->SetPrototype(*value));
 179 }
 180
 181
 182 static int ExpectedNofPropertiesFromEstimate(int estimate) {
 183   // If no properties are added in the constructor, they are more likely
 184   // to be added later.
 185   if (estimate == 0) estimate = 2;
 186
 187   // We do not shrink objects that go into a snapshot (yet), so we adjust
 188   // the estimate conservatively.
 189   if (Serializer::enabled()) return estimate + 2;
 190
 191   // Inobject slack tracking will reclaim redundant inobject space later,
 192   // so we can afford to adjust the estimate generously.
 193   if (FLAG_clever_optimizations) {
 194     return estimate + 8;
 195   } else {
 196     return estimate + 3;
 197   }
 198 }
 199
 200
 201 void SetExpectedNofPropertiesFromEstimate(Handle<SharedFunctionInfo> shared,
 202                                           int estimate) {
 203   // See the comment in SetExpectedNofProperties.
 204   if (shared->live_objects_may_exist()) return;
 205
 206   shared->set_expected_nof_properties(
 207       ExpectedNofPropertiesFromEstimate(estimate));
 208 }
 209
 210
 211 void FlattenString(Handle<String> string) {
 212   CALL_HEAP_FUNCTION_VOID(string->GetIsolate(), string->TryFlatten());
 213 }
 214
 215
 216 Handle<String> FlattenGetString(Handle<String> string) {
 217   CALL_HEAP_FUNCTION(string->GetIsolate(), string->TryFlatten(), String);
 218 }
 219
 220
 221 Handle<Object> SetPrototype(Handle<JSFunction> function,
 222                             Handle<Object> prototype) {
 223   ASSERT(function->should_have_prototype());
 224   CALL_HEAP_FUNCTION(function->GetIsolate(),
 225                      Accessors::FunctionSetPrototype(*function,
 226                                                      *prototype,
 227                                                      NULL),
 228                      Object);
 229 }
 230
 231
 232 Handle<Object> SetProperty(Handle<Object> object,
 233                            Handle<Object> key,
 234                            Handle<Object> value,
 235                            PropertyAttributes attributes,
 236                            StrictModeFlag strict_mode) {
 237   Isolate* isolate = Isolate::Current();
 238   CALL_HEAP_FUNCTION(
 239       isolate,
 240       Runtime::SetObjectProperty(
 241           isolate, object, key, value, attributes, strict_mode),
 242       Object);
 243 }
 244
 245
 246 Handle<Object> ForceSetProperty(Handle<JSObject> object,
 247                                 Handle<Object> key,
 248                                 Handle<Object> value,
 249                                 PropertyAttributes attributes) {
 250   Isolate* isolate = object->GetIsolate();
 251   CALL_HEAP_FUNCTION(
 252       isolate,
 253       Runtime::ForceSetObjectProperty(
 254           isolate, object, key, value, attributes),
 255       Object);
 256 }
 257
 258
 259 Handle<Object> ForceDeleteProperty(Handle<JSObject> object,
 260                                    Handle<Object> key) {
 261   Isolate* isolate = object->GetIsolate();
 262   CALL_HEAP_FUNCTION(isolate,
 263                      Runtime::ForceDeleteObjectProperty(isolate, object, key),
 264                      Object);
 265 }
 266
 267
 268 Handle<Object> SetPropertyWithInterceptor(Handle<JSObject> object,
 269                                           Handle<String> key,
 270                                           Handle<Object> value,
 271                                           PropertyAttributes attributes,
 272                                           StrictModeFlag strict_mode) {
 273   CALL_HEAP_FUNCTION(object->GetIsolate(),
 274                      object->SetPropertyWithInterceptor(*key,
 275                                                         *value,
 276                                                         attributes,
 277                                                         strict_mode),
 278                      Object);
 279 }
 280
 281
 282 Handle<Object> GetProperty(Handle<JSReceiver> obj,
 283                            const char* name) {
 284   Isolate* isolate = obj->GetIsolate();
 285   Handle<String> str = isolate->factory()->LookupAsciiSymbol(name);
 286   CALL_HEAP_FUNCTION(isolate, obj->GetProperty(*str), Object);
 287 }
 288
 289
 290 Handle<Object> GetProperty(Handle<Object> obj,
 291                            Handle<Object> key) {
 292   Isolate* isolate = Isolate::Current();
 293   CALL_HEAP_FUNCTION(isolate,
 294                      Runtime::GetObjectProperty(isolate, obj, key), Object);
 295 }
 296
 297
 298 Handle<Object> GetPropertyWithInterceptor(Handle<JSObject> receiver,
 299                                           Handle<JSObject> holder,
 300                                           Handle<String> name,
 301                                           PropertyAttributes* attributes) {
 302   Isolate* isolate = receiver->GetIsolate();
 303   CALL_HEAP_FUNCTION(isolate,
 304                      holder->GetPropertyWithInterceptor(*receiver,
 305                                                         *name,
 306                                                         attributes),
 307                      Object);
 308 }
 309
 310
 311 Handle<Object> SetPrototype(Handle<JSObject> obj, Handle<Object> value) {
 312   const bool skip_hidden_prototypes = false;
 313   CALL_HEAP_FUNCTION(obj->GetIsolate(),
 314                      obj->SetPrototype(*value, skip_hidden_prototypes), Object);
 315 }
 316
 317
 318 Handle<Object> LookupSingleCharacterStringFromCode(uint32_t index) {
 319   Isolate* isolate = Isolate::Current();
 320   CALL_HEAP_FUNCTION(
 321       isolate,
 322       isolate->heap()->LookupSingleCharacterStringFromCode(index), Object);
 323 }
 324
 325
 326 Handle<String> SubString(Handle<String> str,
 327                          int start,
 328                          int end,
 329                          PretenureFlag pretenure) {
 330   CALL_HEAP_FUNCTION(str->GetIsolate(),
 331                      str->SubString(start, end, pretenure), String);
 332 }
 333
 334
 335 Handle<JSObject> Copy(Handle<JSObject> obj) {
 336   Isolate* isolate = obj->GetIsolate();
 337   CALL_HEAP_FUNCTION(isolate,
 338                      isolate->heap()->CopyJSObject(*obj), JSObject);
 339 }
 340
 341
 342 Handle<Object> SetAccessor(Handle<JSObject> obj, Handle<AccessorInfo> info) {
 343   CALL_HEAP_FUNCTION(obj->GetIsolate(), obj->DefineAccessor(*info), Object);
 344 }
 345
 346
 347 // Wrappers for scripts are kept alive and cached in weak global
 348 // handles referred from foreign objects held by the scripts as long as
 349 // they are used. When they are not used anymore, the garbage
 350 // collector will call the weak callback on the global handle
 351 // associated with the wrapper and get rid of both the wrapper and the
 352 // handle.
 353 static void ClearWrapperCache(Persistent<v8::Value> handle, void*) {
 354   Handle<Object> cache = Utils::OpenHandle(*handle);
 355   JSValue* wrapper = JSValue::cast(*cache);
 356   Foreign* foreign = Script::cast(wrapper->value())->wrapper();
 357   ASSERT(foreign->foreign_address() ==
 358          reinterpret_cast<Address>(cache.location()));
 359   foreign->set_foreign_address(0);
 360   Isolate* isolate = Isolate::Current();
 361   isolate->global_handles()->Destroy(cache.location());
 362   isolate->counters()->script_wrappers()->Decrement();
 363 }
 364
 365
 366 Handle<JSValue> GetScriptWrapper(Handle<Script> script) {
 367   if (script->wrapper()->foreign_address() != NULL) {
 368     // Return the script wrapper directly from the cache.
 369     return Handle<JSValue>(
 370         reinterpret_cast<JSValue**>(script->wrapper()->foreign_address()));
 371   }
 372   Isolate* isolate = Isolate::Current();
 373   // Construct a new script wrapper.
 374   isolate->counters()->script_wrappers()->Increment();
 375   Handle<JSFunction> constructor = isolate->script_function();
 376   Handle<JSValue> result =
 377       Handle<JSValue>::cast(isolate->factory()->NewJSObject(constructor));
 378   result->set_value(*script);
 379
 380   // Create a new weak global handle and use it to cache the wrapper
 381   // for future use. The cache will automatically be cleared by the
 382   // garbage collector when it is not used anymore.
 383   Handle<Object> handle = isolate->global_handles()->Create(*result);
 384   isolate->global_handles()->MakeWeak(handle.location(), NULL,
 385                                       &ClearWrapperCache);
 386   script->wrapper()->set_foreign_address(
 387       reinterpret_cast<Address>(handle.location()));
 388   return result;
 389 }
 390
 391
 392 // Init line_ends array with code positions of line ends inside script
 393 // source.
 394 void InitScriptLineEnds(Handle<Script> script) {
 395   if (!script->line_ends()->IsUndefined()) return;
 396
 397   Isolate* isolate = script->GetIsolate();
 398
 399   if (!script->source()->IsString()) {
 400     ASSERT(script->source()->IsUndefined());
 401     Handle<FixedArray> empty = isolate->factory()->NewFixedArray(0);
 402     script->set_line_ends(*empty);
 403     ASSERT(script->line_ends()->IsFixedArray());
 404     return;
 405   }
 406
 407   Handle<String> src(String::cast(script->source()), isolate);
 408
 409   Handle<FixedArray> array = CalculateLineEnds(src, true);
 410
 411   if (*array != isolate->heap()->empty_fixed_array()) {
 412     array->set_map(isolate->heap()->fixed_cow_array_map());
 413   }
 414
 415   script->set_line_ends(*array);
 416   ASSERT(script->line_ends()->IsFixedArray());
 417 }
 418
 419
 420 template <typename SourceChar>
 421 static void CalculateLineEnds(Isolate* isolate,
 422                               List<int>* line_ends,
 423                               Vector<const SourceChar> src,
 424                               bool with_last_line) {
 425   const int src_len = src.length();
 426   StringSearch<char, SourceChar> search(isolate, CStrVector("\n"));
 427
 428   // Find and record line ends.
 429   int position = 0;
 430   while (position != -1 && position < src_len) {
 431     position = search.Search(src, position);
 432     if (position != -1) {
 433       line_ends->Add(position);
 434       position++;
 435     } else if (with_last_line) {
 436       // Even if the last line misses a line end, it is counted.
 437       line_ends->Add(src_len);
 438       return;
 439     }
 440   }
 441 }
 442
 443
 444 Handle<FixedArray> CalculateLineEnds(Handle<String> src,
 445                                      bool with_last_line) {
 446   src = FlattenGetString(src);
 447   // Rough estimate of line count based on a roughly estimated average
 448   // length of (unpacked) code.
 449   int line_count_estimate = src->length() >> 4;
 450   List<int> line_ends(line_count_estimate);
 451   Isolate* isolate = src->GetIsolate();
 452   {
 453     AssertNoAllocation no_heap_allocation;  // ensure vectors stay valid.
 454     // Dispatch on type of strings.
 455     String::FlatContent content = src->GetFlatContent();
 456     ASSERT(content.IsFlat());
 457     if (content.IsAscii()) {
 458       CalculateLineEnds(isolate,
 459                         &line_ends,
 460                         content.ToAsciiVector(),
 461                         with_last_line);
 462     } else {
 463       CalculateLineEnds(isolate,
 464                         &line_ends,
 465                         content.ToUC16Vector(),
 466                         with_last_line);
 467     }
 468   }
 469   int line_count = line_ends.length();
 470   Handle<FixedArray> array = isolate->factory()->NewFixedArray(line_count);
 471   for (int i = 0; i < line_count; i++) {
 472     array->set(i, Smi::FromInt(line_ends[i]));
 473   }
 474   return array;
 475 }
 476
 477
 478 // Convert code position into line number.
 479 int GetScriptLineNumber(Handle<Script> script, int code_pos) {
 480   InitScriptLineEnds(script);
 481   AssertNoAllocation no_allocation;
 482   FixedArray* line_ends_array = FixedArray::cast(script->line_ends());
 483   const int line_ends_len = line_ends_array->length();
 484
 485   if (!line_ends_len) return -1;
 486
 487   if ((Smi::cast(line_ends_array->get(0)))->value() >= code_pos) {
 488     return script->line_offset()->value();
 489   }
 490
 491   int left = 0;
 492   int right = line_ends_len;
 493   while (int half = (right - left) / 2) {
 494     if ((Smi::cast(line_ends_array->get(left + half)))->value() > code_pos) {
 495       right -= half;
 496     } else {
 497       left += half;
 498     }
 499   }
 500   return right + script->line_offset()->value();
 501 }
 502
 503 // Convert code position into column number.
 504 int GetScriptColumnNumber(Handle<Script> script, int code_pos) {
 505   int line_number = GetScriptLineNumber(script, code_pos);
 506   if (line_number == -1) return -1;
 507
 508   AssertNoAllocation no_allocation;
 509   FixedArray* line_ends_array = FixedArray::cast(script->line_ends());
 510   line_number = line_number - script->line_offset()->value();
 511   if (line_number == 0) return code_pos + script->column_offset()->value();
 512   int prev_line_end_pos =
 513       Smi::cast(line_ends_array->get(line_number - 1))->value();
 514   return code_pos - (prev_line_end_pos + 1);
 515 }
 516
 517 int GetScriptLineNumberSafe(Handle<Script> script, int code_pos) {
 518   AssertNoAllocation no_allocation;
 519   if (!script->line_ends()->IsUndefined()) {
 520     return GetScriptLineNumber(script, code_pos);
 521   }
 522   // Slow mode: we do not have line_ends. We have to iterate through source.
 523   if (!script->source()->IsString()) {
 524     return -1;
 525   }
 526   String* source = String::cast(script->source());
 527   int line = 0;
 528   int len = source->length();
 529   for (int pos = 0; pos < len; pos++) {
 530     if (pos == code_pos) {
 531       break;
 532     }
 533     if (source->Get(pos) == '\n') {
 534       line++;
 535     }
 536   }
 537   return line;
 538 }
 539
 540
 541 void CustomArguments::IterateInstance(ObjectVisitor* v) {
 542   v->VisitPointers(values_, values_ + ARRAY_SIZE(values_));
 543 }
 544
 545
 546 // Compute the property keys from the interceptor.
 547 v8::Handle<v8::Array> GetKeysForNamedInterceptor(Handle<JSReceiver> receiver,
 548                                                  Handle<JSObject> object) {
 549   Isolate* isolate = receiver->GetIsolate();
 550   Handle<InterceptorInfo> interceptor(object->GetNamedInterceptor());
 551   CustomArguments args(isolate, interceptor->data(), *receiver, *object);
 552   v8::AccessorInfo info(args.end());
 553   v8::Handle<v8::Array> result;
 554   if (!interceptor->enumerator()->IsUndefined()) {
 555     v8::NamedPropertyEnumerator enum_fun =
 556         v8::ToCData<v8::NamedPropertyEnumerator>(interceptor->enumerator());
 557     LOG(isolate, ApiObjectAccess("interceptor-named-enum", *object));
 558     {
 559       // Leaving JavaScript.
 560       VMState state(isolate, EXTERNAL);
 561       result = enum_fun(info);
 562     }
 563   }
 564   return result;
 565 }
 566
 567
 568 // Compute the element keys from the interceptor.
 569 v8::Handle<v8::Array> GetKeysForIndexedInterceptor(Handle<JSReceiver> receiver,
 570                                                    Handle<JSObject> object) {
 571   Isolate* isolate = receiver->GetIsolate();
 572   Handle<InterceptorInfo> interceptor(object->GetIndexedInterceptor());
 573   CustomArguments args(isolate, interceptor->data(), *receiver, *object);
 574   v8::AccessorInfo info(args.end());
 575   v8::Handle<v8::Array> result;
 576   if (!interceptor->enumerator()->IsUndefined()) {
 577     v8::IndexedPropertyEnumerator enum_fun =
 578         v8::ToCData<v8::IndexedPropertyEnumerator>(interceptor->enumerator());
 579     LOG(isolate, ApiObjectAccess("interceptor-indexed-enum", *object));
 580     {
 581       // Leaving JavaScript.
 582       VMState state(isolate, EXTERNAL);
 583       result = enum_fun(info);
 584     }
 585   }
 586   return result;
 587 }
 588
 589
 590 static bool ContainsOnlyValidKeys(Handle<FixedArray> array) {
 591   int len = array->length();
 592   for (int i = 0; i < len; i++) {
 593     Object* e = array->get(i);
 594     if (!(e->IsString() || e->IsNumber())) return false;
 595   }
 596   return true;
 597 }
 598
 599
 600 Handle<FixedArray> GetKeysInFixedArrayFor(Handle<JSReceiver> object,
 601                                           KeyCollectionType type,
 602                                           bool* threw) {
 603   USE(ContainsOnlyValidKeys);
 604   Isolate* isolate = object->GetIsolate();
 605   Handle<FixedArray> content = isolate->factory()->empty_fixed_array();
 606   Handle<JSObject> arguments_boilerplate = Handle<JSObject>(
 607       isolate->context()->global_context()->arguments_boilerplate(),
 608       isolate);
 609   Handle<JSFunction> arguments_function = Handle<JSFunction>(
 610       JSFunction::cast(arguments_boilerplate->map()->constructor()),
 611       isolate);
 612
 613   // Only collect keys if access is permitted.
 614   for (Handle<Object> p = object;
 615        *p != isolate->heap()->null_value();
 616        p = Handle<Object>(p->GetPrototype(), isolate)) {
 617     if (p->IsJSProxy()) {
 618       Handle<JSProxy> proxy(JSProxy::cast(*p), isolate);
 619       Handle<Object> args[] = { proxy };
 620       Handle<Object> names = Execution::Call(
 621           isolate->proxy_enumerate(), object, ARRAY_SIZE(args), args, threw);
 622       if (*threw) return content;
 623       content = AddKeysFromJSArray(content, Handle<JSArray>::cast(names));
 624       break;
 625     }
 626
 627     Handle<JSObject> current(JSObject::cast(*p), isolate);
 628
 629     // Check access rights if required.
 630     if (current->IsAccessCheckNeeded() &&
 631         !isolate->MayNamedAccess(*current,
 632                                  isolate->heap()->undefined_value(),
 633                                  v8::ACCESS_KEYS)) {
 634       isolate->ReportFailedAccessCheck(*current, v8::ACCESS_KEYS);
 635       break;
 636     }
 637
 638     // Compute the element keys.
 639     Handle<FixedArray> element_keys =
 640         isolate->factory()->NewFixedArray(current->NumberOfEnumElements());
 641     current->GetEnumElementKeys(*element_keys);
 642     content = UnionOfKeys(content, element_keys);
 643     ASSERT(ContainsOnlyValidKeys(content));
 644
 645     // Add the element keys from the interceptor.
 646     if (current->HasIndexedInterceptor()) {
 647       v8::Handle<v8::Array> result =
 648           GetKeysForIndexedInterceptor(object, current);
 649       if (!result.IsEmpty())
 650         content = AddKeysFromJSArray(content, v8::Utils::OpenHandle(*result));
 651       ASSERT(ContainsOnlyValidKeys(content));
 652     }
 653
 654     // We can cache the computed property keys if access checks are
 655     // not needed and no interceptors are involved.
 656     //
 657     // We do not use the cache if the object has elements and
 658     // therefore it does not make sense to cache the property names
 659     // for arguments objects.  Arguments objects will always have
 660     // elements.
 661     // Wrapped strings have elements, but don't have an elements
 662     // array or dictionary.  So the fast inline test for whether to
 663     // use the cache says yes, so we should not create a cache.
 664     bool cache_enum_keys =
 665         ((current->map()->constructor() != *arguments_function) &&
 666          !current->IsJSValue() &&
 667          !current->IsAccessCheckNeeded() &&
 668          !current->HasNamedInterceptor() &&
 669          !current->HasIndexedInterceptor());
 670     // Compute the property keys and cache them if possible.
 671     content =
 672         UnionOfKeys(content, GetEnumPropertyKeys(current, cache_enum_keys));
 673     ASSERT(ContainsOnlyValidKeys(content));
 674
 675     // Add the property keys from the interceptor.
 676     if (current->HasNamedInterceptor()) {
 677       v8::Handle<v8::Array> result =
 678           GetKeysForNamedInterceptor(object, current);
 679       if (!result.IsEmpty())
 680         content = AddKeysFromJSArray(content, v8::Utils::OpenHandle(*result));
 681       ASSERT(ContainsOnlyValidKeys(content));
 682     }
 683
 684     // If we only want local properties we bail out after the first
 685     // iteration.
 686     if (type == LOCAL_ONLY)
 687       break;
 688   }
 689   return content;
 690 }
 691
 692
 693 Handle<JSArray> GetKeysFor(Handle<JSReceiver> object, bool* threw) {
 694   Isolate* isolate = object->GetIsolate();
 695   isolate->counters()->for_in()->Increment();
 696   Handle<FixedArray> elements =
 697       GetKeysInFixedArrayFor(object, INCLUDE_PROTOS, threw);
 698   return isolate->factory()->NewJSArrayWithElements(elements);
 699 }
 700
 701
 702 Handle<FixedArray> GetEnumPropertyKeys(Handle<JSObject> object,
 703                                        bool cache_result) {
 704   int index = 0;
 705   Isolate* isolate = object->GetIsolate();
 706   if (object->HasFastProperties()) {
 707     if (object->map()->instance_descriptors()->HasEnumCache()) {
 708       isolate->counters()->enum_cache_hits()->Increment();
 709       DescriptorArray* desc = object->map()->instance_descriptors();
 710       return Handle<FixedArray>(FixedArray::cast(desc->GetEnumCache()),
 711                                 isolate);
 712     }
 713     isolate->counters()->enum_cache_misses()->Increment();
 714     Handle<Map> map(object->map());
 715     int num_enum = object->NumberOfLocalProperties(DONT_ENUM);
 716
 717     Handle<FixedArray> storage = isolate->factory()->NewFixedArray(num_enum);
 718     Handle<FixedArray> sort_array = isolate->factory()->NewFixedArray(num_enum);
 719
 720     Handle<FixedArray> indices;
 721     Handle<FixedArray> sort_array2;
 722
 723     if (cache_result) {
 724       indices = isolate->factory()->NewFixedArray(num_enum);
 725       sort_array2 = isolate->factory()->NewFixedArray(num_enum);
 726     }
 727
 728     Handle<DescriptorArray> descs =
 729         Handle<DescriptorArray>(object->map()->instance_descriptors(), isolate);
 730
 731     for (int i = 0; i < descs->number_of_descriptors(); i++) {
 732       if (descs->IsProperty(i) && !descs->GetDetails(i).IsDontEnum()) {
 733         storage->set(index, descs->GetKey(i));
 734         PropertyDetails details = descs->GetDetails(i);
 735         sort_array->set(index, Smi::FromInt(details.index()));
 736         if (!indices.is_null()) {
 737           if (details.type() != FIELD) {
 738             indices = Handle<FixedArray>();
 739             sort_array2 = Handle<FixedArray>();
 740           } else {
 741             int field_index = Descriptor::IndexFromValue(descs->GetValue(i));
 742             if (field_index >= map->inobject_properties()) {
 743               field_index = -(field_index - map->inobject_properties() + 1);
 744             }
 745             indices->set(index, Smi::FromInt(field_index));
 746             sort_array2->set(index, Smi::FromInt(details.index()));
 747           }
 748         }
 749         index++;
 750       }
 751     }
 752     storage->SortPairs(*sort_array, sort_array->length());
 753     if (!indices.is_null()) {
 754       indices->SortPairs(*sort_array2, sort_array2->length());
 755     }
 756     if (cache_result) {
 757       Handle<FixedArray> bridge_storage =
 758           isolate->factory()->NewFixedArray(
 759               DescriptorArray::kEnumCacheBridgeLength);
 760       DescriptorArray* desc = object->map()->instance_descriptors();
 761       desc->SetEnumCache(*bridge_storage,
 762                          *storage,
 763                          indices.is_null() ? Object::cast(Smi::FromInt(0))
 764                                            : Object::cast(*indices));
 765     }
 766     ASSERT(storage->length() == index);
 767     return storage;
 768   } else {
 769     int num_enum = object->NumberOfLocalProperties(DONT_ENUM);
 770     Handle<FixedArray> storage = isolate->factory()->NewFixedArray(num_enum);
 771     Handle<FixedArray> sort_array = isolate->factory()->NewFixedArray(num_enum);
 772     object->property_dictionary()->CopyEnumKeysTo(*storage, *sort_array);
 773     return storage;
 774   }
 775 }
 776
 777
 778 Handle<ObjectHashSet> ObjectHashSetAdd(Handle<ObjectHashSet> table,
 779                                        Handle<Object> key) {
 780   CALL_HEAP_FUNCTION(table->GetIsolate(),
 781                      table->Add(*key),
 782                      ObjectHashSet);
 783 }
 784
 785
 786 Handle<ObjectHashSet> ObjectHashSetRemove(Handle<ObjectHashSet> table,
 787                                           Handle<Object> key) {
 788   CALL_HEAP_FUNCTION(table->GetIsolate(),
 789                      table->Remove(*key),
 790                      ObjectHashSet);
 791 }
 792
 793
 794 Handle<ObjectHashTable> PutIntoObjectHashTable(Handle<ObjectHashTable> table,
 795                                                Handle<Object> key,
 796                                                Handle<Object> value) {
 797   CALL_HEAP_FUNCTION(table->GetIsolate(),
 798                      table->Put(*key, *value),
 799                      ObjectHashTable);
 800 }
 801
 802
 803 // This method determines the type of string involved and then gets the UTF8
 804 // length of the string.  It doesn't flatten the string and has log(n) recursion
 805 // for a string of length n.  If the failure flag gets set, then we have to
 806 // flatten the string and retry.  Failures are caused by surrogate pairs in deep
 807 // cons strings.
 808
 809 // Single surrogate characters that are encountered in the UTF-16 character
 810 // sequence of the input string get counted as 3 UTF-8 bytes, because that
 811 // is the way that WriteUtf8 will encode them.  Surrogate pairs are counted and
 812 // encoded as one 4-byte UTF-8 sequence.
 813
 814 // This function conceptually uses recursion on the two halves of cons strings.
 815 // However, in order to avoid the recursion going too deep it recurses on the
 816 // second string of the cons, but iterates on the first substring (by manually
 817 // eliminating it as a tail recursion).  This means it counts the UTF-8 length
 818 // from the end to the start, which makes no difference to the total.
 819
 820 // Surrogate pairs are recognized even if they are split across two sides of a
 821 // cons, which complicates the implementation somewhat.  Therefore, too deep
 822 // recursion cannot always be avoided.  This case is detected, and the failure
 823 // flag is set, a signal to the caller that the string should be flattened and
 824 // the operation retried.
 825 int Utf8LengthHelper(String* input,
 826                      int from,
 827                      int to,
 828                      bool followed_by_surrogate,
 829                      int max_recursion,
 830                      bool* failure,
 831                      bool* starts_with_surrogate) {
 832   if (from == to) return 0;
 833   int total = 0;
 834   bool dummy;
 835   while (true) {
 836     if (input->IsAsciiRepresentation()) {
 837       *starts_with_surrogate = false;
 838       return total + to - from;
 839     }
 840     switch (StringShape(input).representation_tag()) {
 841       case kConsStringTag: {
 842         ConsString* str = ConsString::cast(input);
 843         String* first = str->first();
 844         String* second = str->second();
 845         int first_length = first->length();
 846         if (first_length - from > to - first_length) {
 847           if (first_length < to) {
 848             // Right hand side is shorter.  No need to check the recursion depth
 849             // since this can only happen log(n) times.
 850             bool right_starts_with_surrogate = false;
 851             total += Utf8LengthHelper(second,
 852                                       0,
 853                                       to - first_length,
 854                                       followed_by_surrogate,
 855                                       max_recursion - 1,
 856                                       failure,
 857                                       &right_starts_with_surrogate);
 858             if (*failure) return 0;
 859             followed_by_surrogate = right_starts_with_surrogate;
 860             input = first;
 861             to = first_length;
 862           } else {
 863             // We only need the left hand side.
 864             input = first;
 865           }
 866         } else {
 867           if (first_length > from) {
 868             // Left hand side is shorter.
 869             if (first->IsAsciiRepresentation()) {
 870               total += first_length - from;
 871               *starts_with_surrogate = false;
 872               starts_with_surrogate = &dummy;
 873               input = second;
 874               from = 0;
 875               to -= first_length;
 876             } else if (second->IsAsciiRepresentation()) {
 877               followed_by_surrogate = false;
 878               total += to - first_length;
 879               input = first;
 880               to = first_length;
 881             } else if (max_recursion > 0) {
 882               bool right_starts_with_surrogate = false;
 883               // Recursing on the long one.  This may fail.
 884               total += Utf8LengthHelper(second,
 885                                         0,
 886                                         to - first_length,
 887                                         followed_by_surrogate,
 888                                         max_recursion - 1,
 889                                         failure,
 890                                         &right_starts_with_surrogate);
 891               if (*failure) return 0;
 892               input = first;
 893               to = first_length;
 894               followed_by_surrogate = right_starts_with_surrogate;
 895             } else {
 896               *failure = true;
 897               return 0;
 898             }
 899           } else {
 900             // We only need the right hand side.
 901             input = second;
 902             from = 0;
 903             to -= first_length;
 904           }
 905         }
 906         continue;
 907       }
 908       case kExternalStringTag:
 909       case kSeqStringTag: {
 910         Vector<const uc16> vector = input->GetFlatContent().ToUC16Vector();
 911         const uc16* p = vector.start();
 912         int previous = unibrow::Utf16::kNoPreviousCharacter;
 913         for (int i = from; i < to; i++) {
 914           uc16 c = p[i];
 915           total += unibrow::Utf8::Length(c, previous);
 916           previous = c;
 917         }
 918         if (to - from > 0) {
 919           if (unibrow::Utf16::IsLeadSurrogate(previous) &&
 920               followed_by_surrogate) {
 921             total -= unibrow::Utf8::kBytesSavedByCombiningSurrogates;
 922           }
 923           if (unibrow::Utf16::IsTrailSurrogate(p[from])) {
 924             *starts_with_surrogate = true;
 925           }
 926         }
 927         return total;
 928       }
 929       case kSlicedStringTag: {
 930         SlicedString* str = SlicedString::cast(input);
 931         int offset = str->offset();
 932         input = str->parent();
 933         from += offset;
 934         to += offset;
 935         continue;
 936       }
 937       default:
 938         break;
 939     }
 940     UNREACHABLE();
 941     return 0;
 942   }
 943   return 0;
 944 }
 945
 946
 947 int Utf8Length(Handle<String> str) {
 948   bool dummy;
 949   bool failure;
 950   int len;
 951   const int kRecursionBudget = 100;
 952   do {
 953     failure = false;
 954     len = Utf8LengthHelper(
 955         *str, 0, str->length(), false, kRecursionBudget, &failure, &dummy);
 956     if (failure) FlattenString(str);
 957   } while (failure);
 958   return len;
 959 }
 960
 961 } }  // namespace v8::internal