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 "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
44namespace v8 {
45namespace internal {
46
47
48int 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
58Object** 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
99void 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
107void 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
115Address HandleScope::current_level_address() {
116  return reinterpret_cast<Address>(
117      &Isolate::Current()->handle_scope_data()->level);
118}
119
120
121Address HandleScope::current_next_address() {
122  return reinterpret_cast<Address>(
123      &Isolate::Current()->handle_scope_data()->next);
124}
125
126
127Address HandleScope::current_limit_address() {
128  return reinterpret_cast<Address>(
129      &Isolate::Current()->handle_scope_data()->limit);
130}
131
132
133Handle<FixedArray> AddKeysFromJSArray(Handle<FixedArray> content,
134                                      Handle<JSArray> array) {
135  CALL_HEAP_FUNCTION(content->GetIsolate(),
136                     content->AddKeysFromJSArray(*array), FixedArray);
137}
138
139
140Handle<FixedArray> UnionOfKeys(Handle<FixedArray> first,
141                               Handle<FixedArray> second) {
142  CALL_HEAP_FUNCTION(first->GetIsolate(),
143                     first->UnionOfKeys(*second), FixedArray);
144}
145
146
147Handle<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
157void 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
176void SetPrototypeProperty(Handle<JSFunction> func, Handle<JSObject> value) {
177  CALL_HEAP_FUNCTION_VOID(func->GetIsolate(),
178                          func->SetPrototype(*value));
179}
180
181
182static 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
201void 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
211void FlattenString(Handle<String> string) {
212  CALL_HEAP_FUNCTION_VOID(string->GetIsolate(), string->TryFlatten());
213}
214
215
216Handle<String> FlattenGetString(Handle<String> string) {
217  CALL_HEAP_FUNCTION(string->GetIsolate(), string->TryFlatten(), String);
218}
219
220
221Handle<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
232Handle<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
246Handle<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
259Handle<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
268Handle<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
282Handle<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
290Handle<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
298Handle<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
311Handle<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
318Handle<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
326Handle<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
335Handle<JSObject> Copy(Handle<JSObject> obj) {
336  Isolate* isolate = obj->GetIsolate();
337  CALL_HEAP_FUNCTION(isolate,
338                     isolate->heap()->CopyJSObject(*obj), JSObject);
339}
340
341
342Handle<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.
353static 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
366Handle<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.
394void 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
420template <typename SourceChar>
421static 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
444Handle<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.
479int 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.
504int 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
517int 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
541void CustomArguments::IterateInstance(ObjectVisitor* v) {
542  v->VisitPointers(values_, values_ + ARRAY_SIZE(values_));
543}
544
545
546// Compute the property keys from the interceptor.
547v8::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.
569v8::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
590static 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
600Handle<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
693Handle<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
702Handle<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->IsDontEnum(i)) {
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
778Handle<ObjectHashSet> ObjectHashSetAdd(Handle<ObjectHashSet> table,
779                                       Handle<Object> key) {
780  CALL_HEAP_FUNCTION(table->GetIsolate(),
781                     table->Add(*key),
782                     ObjectHashSet);
783}
784
785
786Handle<ObjectHashSet> ObjectHashSetRemove(Handle<ObjectHashSet> table,
787                                          Handle<Object> key) {
788  CALL_HEAP_FUNCTION(table->GetIsolate(),
789                     table->Remove(*key),
790                     ObjectHashSet);
791}
792
793
794Handle<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.
825int 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
947int 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
962