Merge changes from bleeding_edge into experimental toiger branch....

src/runtime.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1043 matching lines @@
   }
  private:
   int suffixes_[kBMMaxShift + 1];
   int good_suffix_shift_[kBMMaxShift + 1];
   int* biased_suffixes_;
   int* biased_good_suffix_shift_;
   DISALLOW_COPY_AND_ASSIGN(BMGoodSuffixBuffers);
 };
 
 // buffers reused by BoyerMoore
-static int bad_char_occurence[kBMAlphabetSize];
+static int bad_char_occurrence[kBMAlphabetSize];
 static BMGoodSuffixBuffers bmgs_buffers;
 
 // Compute the bad-char table for Boyer-Moore in the static buffer.
 template <typename pchar>
 static void BoyerMoorePopulateBadCharTable(Vector<const pchar> pattern,
                                           int start) {
   // Run forwards to populate bad_char_table, so that *last* instance
   // of character equivalence class is the one registered.
   // Notice: Doesn't include the last character.
   int table_size = (sizeof(pchar) == 1) ? String::kMaxAsciiCharCode + 1
                                         : kBMAlphabetSize;
   if (start == 0) {  // All patterns less than kBMMaxShift in length.
-    memset(bad_char_occurence, -1, table_size * sizeof(*bad_char_occurence));
+    memset(bad_char_occurrence, -1, table_size * sizeof(*bad_char_occurrence));
   } else {
     for (int i = 0; i < table_size; i++) {
-      bad_char_occurence[i] = start - 1;
+      bad_char_occurrence[i] = start - 1;
     }
   }
   for (int i = start; i < pattern.length() - 1; i++) {
     pchar c = pattern[i];
     int bucket = (sizeof(pchar) ==1) ? c : c % kBMAlphabetSize;
-    bad_char_occurence[bucket] = i;
+    bad_char_occurrence[bucket] = i;
   }
 }
 
 template <typename pchar>
 static void BoyerMoorePopulateGoodSuffixTable(Vector<const pchar> pattern,
                                               int start) {
   int m = pattern.length();
   int len = m - start;
   // Compute Good Suffix tables.
   bmgs_buffers.init(m);
@@ skipping 34 matching lines @@
         bmgs_buffers.shift(i) = suffix - start;
       }
       if (i == suffix) {
         suffix = bmgs_buffers.suffix(suffix);
       }
     }
   }
 }
 
 template <typename schar, typename pchar>
-static inline int CharOccurence(int char_code) {
+static inline int CharOccurrence(int char_code) {
   if (sizeof(schar) == 1) {
-    return bad_char_occurence[char_code];
+    return bad_char_occurrence[char_code];
   }
   if (sizeof(pchar) == 1) {
     if (char_code > String::kMaxAsciiCharCode) {
       return -1;
     }
-    return bad_char_occurence[char_code];
+    return bad_char_occurrence[char_code];
   }
-  return bad_char_occurence[char_code % kBMAlphabetSize];
+  return bad_char_occurrence[char_code % kBMAlphabetSize];
 }
 
-// Restricted simplified Boyer-Moore string matching. Restricts tables to a
-// suffix of long pattern strings and handles only equivalence classes
-// of the full alphabet. This allows us to ensure that tables take only
-// a fixed amount of space.
+// Restricted simplified Boyer-Moore string matching.
+// Uses only the bad-shift table of Boyer-Moore and only uses it
+// for the character compared to the last character of the needle.
 template <typename schar, typename pchar>
-static int BoyerMooreSimplified(Vector<const schar> subject,
-                                Vector<const pchar> pattern,
-                                int start_index,
-                                bool* complete) {
+static int BoyerMooreHorsepool(Vector<const schar> subject,
+                               Vector<const pchar> pattern,
+                               int start_index,
+                               bool* complete) {
   int n = subject.length();
   int m = pattern.length();
   // Only preprocess at most kBMMaxShift last characters of pattern.
   int start = m < kBMMaxShift ? 0 : m - kBMMaxShift;
 
   BoyerMoorePopulateBadCharTable(pattern, start);
 
   int badness = -m;  // How bad we are doing without a good-suffix table.
   int idx;  // No matches found prior to this index.
   pchar last_char = pattern[m - 1];
+  int last_char_shift = m - 1 - CharOccurrence<schar, pchar>(last_char);
   // Perform search
   for (idx = start_index; idx <= n - m;) {
     int j = m - 1;
     int c;
     while (last_char != (c = subject[idx + j])) {
-      int bc_occ = CharOccurence<schar, pchar>(c);
+      int bc_occ = CharOccurrence<schar, pchar>(c);
       int shift = j - bc_occ;
       idx += shift;
       badness += 1 - shift;  // at most zero, so badness cannot increase.
       if (idx > n - m) {
         *complete = true;
         return -1;
       }
     }
     j--;
-    while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--;
+    while (j >= 0 && pattern[j] == (subject[idx + j])) j--;
     if (j < 0) {
       *complete = true;
       return idx;
     } else {
-      int bc_occ = CharOccurence<schar, pchar>(c);
-      int shift = bc_occ < j ? j - bc_occ : 1;
-      idx += shift;
+      idx += last_char_shift;
       // Badness increases by the number of characters we have
       // checked, and decreases by the number of characters we
       // can skip by shifting. It's a measure of how we are doing
       // compared to reading each character exactly once.
-      badness += (m - j) - shift;
+      badness += (m - j) - last_char_shift;
       if (badness > 0) {
         *complete = false;
         return idx;
       }
     }
   }
   *complete = true;
   return -1;
 }
 
 
 template <typename schar, typename pchar>
 static int BoyerMooreIndexOf(Vector<const schar> subject,
                              Vector<const pchar> pattern,
                              int idx) {
   int n = subject.length();
   int m = pattern.length();
   // Only preprocess at most kBMMaxShift last characters of pattern.
   int start = m < kBMMaxShift ? 0 : m - kBMMaxShift;
 
   // Build the Good Suffix table and continue searching.
   BoyerMoorePopulateGoodSuffixTable(pattern, start);
   pchar last_char = pattern[m - 1];
   // Continue search from i.
   do {
     int j = m - 1;
     schar c;
     while (last_char != (c = subject[idx + j])) {
-      int shift = j - CharOccurence<schar, pchar>(c);
+      int shift = j - CharOccurrence<schar, pchar>(c);
       idx += shift;
       if (idx > n - m) {
         return -1;
       }
     }
     while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--;
     if (j < 0) {
       return idx;
     } else if (j < start) {
       // we have matched more than our tables allow us to be smart about.
-      idx += 1;
+      // Fall back on BMH shift.
+      idx += m - 1 - CharOccurrence<schar, pchar>(last_char);
     } else {
       int gs_shift = bmgs_buffers.shift(j + 1);       // Good suffix shift.
-      int bc_occ = CharOccurence<schar, pchar>(c);
+      int bc_occ = CharOccurrence<schar, pchar>(c);
       int shift = j - bc_occ;                         // Bad-char shift.
-      shift = (gs_shift > shift) ? gs_shift : shift;
+      if (gs_shift > shift) {
+        shift = gs_shift;
+      }
       idx += shift;
     }
   } while (idx <= n - m);
 
   return -1;
 }
 
 
 template <typename schar>
 static int SingleCharIndexOf(Vector<const schar> string,
@@ skipping 23 matching lines @@
   // algorithm.
   int badness = -10 - (pattern.length() << 2);
   // We know our pattern is at least 2 characters, we cache the first so
   // the common case of the first character not matching is faster.
   pchar pattern_first_char = pattern[0];
 
   for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) {
     badness++;
     if (badness > 0) {
       *complete = false;
-      return (i);
+      return i;
     }
     if (subject[i] != pattern_first_char) continue;
     int j = 1;
     do {
       if (pattern[j] != subject[i+j]) {
         break;
       }
       j++;
     } while (j < pattern.length());
     if (j == pattern.length()) {
@@ skipping 50 matching lines @@
   if (pat.length() < kBMMinPatternLength) {
     // We don't believe fancy searching can ever be more efficient.
     // The max shift of Boyer-Moore on a pattern of this length does
     // not compensate for the overhead.
     return SimpleIndexOf(sub, pat, start_index);
   }
   // Try algorithms in order of increasing setup cost and expected performance.
   bool complete;
   int idx = SimpleIndexOf(sub, pat, start_index, &complete);
   if (complete) return idx;
-  idx = BoyerMooreSimplified(sub, pat, idx, &complete);
+  idx = BoyerMooreHorsepool(sub, pat, idx, &complete);
   if (complete) return idx;
   return BoyerMooreIndexOf(sub, pat, idx);
 }
 
 // Perform string match of pattern on subject, starting at start index.
 // Caller must ensure that 0 <= start_index <= sub->length(),
 // and should check that pat->length() + start_index <= sub->length()
 int Runtime::StringMatch(Handle<String> sub,
                          Handle<String> pat,
                          int start_index) {
@@ skipping 1944 matching lines @@
 
 
 static Object* Runtime_NewObject(Arguments args) {
   NoHandleAllocation ha;
   ASSERT(args.length() == 1);
 
   Object* constructor = args[0];
   if (constructor->IsJSFunction()) {
     JSFunction* function = JSFunction::cast(constructor);
 
-    // Handle steping into constructors.
+    // Handle steping into constructors if step into is active.
     if (Debug::StepInActive()) {
-      StackFrameIterator it;
-      it.Advance();
-      ASSERT(it.frame()->is_construct());
-      it.Advance();
-      if (it.frame()->fp() == Debug::step_in_fp()) {
-        HandleScope scope;
-        Debug::FloodWithOneShot(Handle<SharedFunctionInfo>(function->shared()));
-      }
+      HandleScope scope;
+      Debug::HandleStepIn(Handle<JSFunction>(function), 0, true);
     }
 
     if (function->has_initial_map() &&
         function->initial_map()->instance_type() == JS_FUNCTION_TYPE) {
       // The 'Function' function ignores the receiver object when
       // called using 'new' and creates a new JSFunction object that
       // is returned.  The receiver object is only used for error
       // reporting if an error occurs when constructing the new
       // JSFunction.  AllocateJSObject should not be used to allocate
       // JSFunctions since it does not properly initialize the shared
@@ skipping 75 matching lines @@
   CONVERT_CHECKED(JSFunction, function, args[0]);
   int length = ScopeInfo<>::NumberOfContextSlots(function->code());
   Object* result = Heap::AllocateFunctionContext(length, function);
   if (result->IsFailure()) return result;
 
   Top::set_context(Context::cast(result));
 
   return result;  // non-failure
 }
 
-
-static Object* Runtime_PushContext(Arguments args) {
-  NoHandleAllocation ha;
-  ASSERT(args.length() == 1);
-
+static Object* PushContextHelper(Object* object, bool is_catch_context) {
   // Convert the object to a proper JavaScript object.
-  Object* object = args[0];
-  if (!object->IsJSObject()) {
-    object = object->ToObject();
-    if (object->IsFailure()) {
-      if (!Failure::cast(object)->IsInternalError()) return object;
+  Object* js_object = object;
+  if (!js_object->IsJSObject()) {
+    js_object = js_object->ToObject();
+    if (js_object->IsFailure()) {
+      if (!Failure::cast(js_object)->IsInternalError()) return js_object;
       HandleScope scope;
-      Handle<Object> handle(args[0]);
+      Handle<Object> handle(object);
       Handle<Object> result =
           Factory::NewTypeError("with_expression", HandleVector(&handle, 1));
       return Top::Throw(*result);
     }
   }
 
   Object* result =
-      Heap::AllocateWithContext(Top::context(), JSObject::cast(object));
+      Heap::AllocateWithContext(Top::context(),
+                                JSObject::cast(js_object),
+                                is_catch_context);
   if (result->IsFailure()) return result;
 
-  Top::set_context(Context::cast(result));
+  Context* context = Context::cast(result);
+  Top::set_context(context);
 
   return result;
 }
 
 
+static Object* Runtime_PushContext(Arguments args) {
+  NoHandleAllocation ha;
+  ASSERT(args.length() == 1);
+  return PushContextHelper(args[0], false);
+}
+
+
+static Object* Runtime_PushCatchContext(Arguments args) {
+  NoHandleAllocation ha;
+  ASSERT(args.length() == 1);
+  return PushContextHelper(args[0], true);
+}
+
+
 static Object* Runtime_LookupContext(Arguments args) {
   HandleScope scope;
   ASSERT(args.length() == 2);
 
   CONVERT_ARG_CHECKED(Context, context, 0);
   CONVERT_ARG_CHECKED(String, name, 1);
 
   int index;
   PropertyAttributes attributes;
   ContextLookupFlags flags = FOLLOW_CHAINS;
@@ skipping 77 matching lines @@
     Object* value = (holder->IsContext())
         ? Context::cast(*holder)->get(index)
         : JSObject::cast(*holder)->GetElement(index);
     return MakePair(Unhole(value, attributes), receiver);
   }
 
   // If the holder is found, we read the property from it.
   if (!holder.is_null() && holder->IsJSObject()) {
     ASSERT(Handle<JSObject>::cast(holder)->HasProperty(*name));
     JSObject* object = JSObject::cast(*holder);
-    JSObject* receiver = (object->IsGlobalObject())
-        ? GlobalObject::cast(object)->global_receiver()
-        : ComputeReceiverForNonGlobal(object);
+    JSObject* receiver;
+    if (object->IsGlobalObject()) {
+      receiver = GlobalObject::cast(object)->global_receiver();
+    } else if (context->is_exception_holder(*holder)) {
+      receiver = Top::context()->global()->global_receiver();
+    } else {
+      receiver = ComputeReceiverForNonGlobal(object);
+    }
     // No need to unhole the value here. This is taken care of by the
     // GetProperty function.
     Object* value = object->GetProperty(*name);
     return MakePair(value, receiver);
   }
 
   if (throw_error) {
     // The property doesn't exist - throw exception.
     Handle<Object> reference_error =
         Factory::NewReferenceError("not_defined", HandleVector(&name, 1));
@@ skipping 1643 matching lines @@
                                             Handle<Context> function_context) {
   // At the bottom of the chain. Return the function context to link to.
   if (context_chain->is_function_context()) {
     return function_context;
   }
 
   // Recursively copy the with contexts.
   Handle<Context> previous(context_chain->previous());
   Handle<JSObject> extension(JSObject::cast(context_chain->extension()));
   return Factory::NewWithContext(
-      CopyWithContextChain(function_context, previous), extension);
+      CopyWithContextChain(function_context, previous),
+      extension,
+      context_chain->IsCatchContext());
 }
 
 
 // Helper function to find or create the arguments object for
 // Runtime_DebugEvaluate.
 static Handle<Object> GetArgumentsObject(JavaScriptFrame* frame,
                                          Handle<JSFunction> function,
                                          Handle<Code> code,
                                          const ScopeInfo<>* sinfo,
                                          Handle<Context> function_context) {
@@ skipping 638 matching lines @@
   } else {
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     Counters::gc_last_resort_from_js.Increment();
     Heap::CollectAllGarbage();
   }
 }
 
 
 } }  // namespace v8::internal