Wire Regexp2000 up to the normal JS RegExp object.

src/jsregexp.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 22 matching lines @@
 #include "ast.h"
 #include "execution.h"
 #include "factory.h"
 #include "jsregexp-inl.h"
 #include "platform.h"
 #include "runtime.h"
 #include "top.h"
 #include "compilation-cache.h"
 #include "string-stream.h"
 #include "parser.h"
+#include "assembler-re2k.h"
 #include "regexp-macro-assembler.h"
+#include "regexp-macro-assembler-re2k.h"
+#include "interpreter-re2k.h"
 
 // Including pcre.h undefines DEBUG to avoid getting debug output from
 // the JSCRE implementation. Make sure to redefine it in debug mode
 // after having included the header file.
 #ifdef DEBUG
 #include "third_party/jscre/pcre.h"
 #define DEBUG
 #else
 #include "third_party/jscre/pcre.h"
 #endif
 
 
 namespace v8 { namespace internal {
 
 
-#define CAPTURE_INDEX 0
-#define INTERNAL_INDEX 1
-
 static Failure* malloc_failure;
 
 static void* JSREMalloc(size_t size) {
   Object* obj = Heap::AllocateByteArray(size);
 
   // If allocation failed, return a NULL pointer to JSRE, and jsRegExpCompile
   // will return NULL to the caller, performs GC there.
   // Also pass failure information to the caller.
   if (obj->IsFailure()) {
     malloc_failure = Failure::cast(obj);
@@ skipping 150 matching lines @@
     if (atom != NULL && !flags.is_ignore_case()) {
       if (parse_result.has_character_escapes) {
         Vector<const uc16> atom_pattern = atom->data();
         Handle<String> atom_string =
             Factory::NewStringFromTwoByte(atom_pattern);
         result = AtomCompile(re, pattern, flags, atom_string);
       } else {
         result = AtomCompile(re, pattern, flags, pattern);
       }
     } else {
-      result = JsrePrepare(re, pattern, flags);
+      RegExpNode* node = NULL;
+      Handle<FixedArray> re2k_data =
+          RegExpEngine::Compile(&parse_result, &node);
+      if (re2k_data.is_null()) {
+        result = JscrePrepare(re, pattern, flags);
+      } else {
+        result = Re2kPrepare(re, pattern, flags, re2k_data);
+      }
     }
     Object* data = re->data();
     if (data->IsFixedArray()) {
       // If compilation succeeded then the data is set on the regexp
       // and we can store it in the cache.
       Handle<FixedArray> data(FixedArray::cast(re->data()));
       CompilationCache::PutRegExp(pattern, flags, data);
     }
   }
 
   LOG(RegExpCompileEvent(re, in_cache));
   return result;
 }
 
 
 Handle<Object> RegExpImpl::Exec(Handle<JSRegExp> regexp,
                                 Handle<String> subject,
                                 Handle<Object> index) {
   switch (regexp->TypeTag()) {
     case JSRegExp::JSCRE:
-      return JsreExec(regexp, subject, index);
+      return JscreExec(regexp, subject, index);
     case JSRegExp::ATOM:
       return AtomExec(regexp, subject, index);
+    case JSRegExp::RE2K:
+      return Re2kExec(regexp, subject, index);
     default:
       UNREACHABLE();
       return Handle<Object>();
   }
 }
 
 
 Handle<Object> RegExpImpl::ExecGlobal(Handle<JSRegExp> regexp,
                                 Handle<String> subject) {
   switch (regexp->TypeTag()) {
     case JSRegExp::JSCRE:
-      return JsreExecGlobal(regexp, subject);
+      return JscreExecGlobal(regexp, subject);
     case JSRegExp::ATOM:
       return AtomExecGlobal(regexp, subject);
+    case JSRegExp::RE2K:
+      return Re2kExecGlobal(regexp, subject);
     default:
       UNREACHABLE();
       return Handle<Object>();
   }
 }
 
 
 Handle<Object> RegExpImpl::AtomCompile(Handle<JSRegExp> re,
                                        Handle<String> pattern,
                                        JSRegExp::Flags flags,
@@ skipping 11 matching lines @@
   uint32_t start_index;
   if (!Array::IndexFromObject(*index, &start_index)) {
     return Handle<Smi>(Smi::FromInt(-1));
   }
 
   LOG(RegExpExecEvent(re, start_index, subject));
   int value = Runtime::StringMatch(subject, needle, start_index);
   if (value == -1) return Factory::null_value();
 
   Handle<FixedArray> array = Factory::NewFixedArray(2);
-  array->set(0,
-             Smi::FromInt(value),
-             SKIP_WRITE_BARRIER);
-  array->set(1,
-             Smi::FromInt(value + needle->length()),
-             SKIP_WRITE_BARRIER);
+  array->set(0, Smi::FromInt(value));
+  array->set(1, Smi::FromInt(value + needle->length()));
   return Factory::NewJSArrayWithElements(array);
 }
 
 
 Handle<Object> RegExpImpl::AtomExecGlobal(Handle<JSRegExp> re,
                                           Handle<String> subject) {
   Handle<String> needle(String::cast(re->DataAt(JSRegExp::kAtomPatternIndex)));
   Handle<JSArray> result = Factory::NewJSArray(1);
   int index = 0;
   int match_count = 0;
   int subject_length = subject->length();
   int needle_length = needle->length();
   while (true) {
     LOG(RegExpExecEvent(re, index, subject));
     int value = -1;
     if (index + needle_length <= subject_length) {
       value = Runtime::StringMatch(subject, needle, index);
     }
     if (value == -1) break;
     HandleScope scope;
     int end = value + needle_length;
 
     Handle<FixedArray> array = Factory::NewFixedArray(2);
-    array->set(0,
-               Smi::FromInt(value),
-               SKIP_WRITE_BARRIER);
-    array->set(1,
-               Smi::FromInt(end),
-               SKIP_WRITE_BARRIER);
+    array->set(0, Smi::FromInt(value));
+    array->set(1, Smi::FromInt(end));
     Handle<JSArray> pair = Factory::NewJSArrayWithElements(array);
     SetElement(result, match_count, pair);
     match_count++;
     index = end;
     if (needle_length == 0) index++;
   }
   return result;
 }
 
 
-Handle<Object>RegExpImpl::JsrePrepare(Handle<JSRegExp> re,
-                                      Handle<String> pattern,
-                                      JSRegExp::Flags flags) {
+Handle<Object>RegExpImpl::JscrePrepare(Handle<JSRegExp> re,
+                                       Handle<String> pattern,
+                                       JSRegExp::Flags flags) {
   Handle<Object> value(Heap::undefined_value());
   Factory::SetRegExpData(re, JSRegExp::JSCRE, pattern, flags, value);
   return re;
 }
 
 
+Handle<Object>RegExpImpl::Re2kPrepare(Handle<JSRegExp> re,
+                                      Handle<String> pattern,
+                                      JSRegExp::Flags flags,
+                                      Handle<FixedArray> re2k_data) {
+  Factory::SetRegExpData(re, JSRegExp::RE2K, pattern, flags, re2k_data);
+  return re;
+}
+
+
 static inline Object* DoCompile(String* pattern,
                                 JSRegExp::Flags flags,
                                 unsigned* number_of_captures,
                                 const char** error_message,
                                 JscreRegExp** code) {
   JSRegExpIgnoreCaseOption case_option = flags.is_ignore_case()
     ? JSRegExpIgnoreCase
     : JSRegExpDoNotIgnoreCase;
   JSRegExpMultilineOption multiline_option = flags.is_multiline()
     ? JSRegExpMultiline
@@ skipping 26 matching lines @@
                              const char** error_message,
                              JscreRegExp** code) {
   CALL_HEAP_FUNCTION_VOID(DoCompile(*pattern,
                                     flags,
                                     number_of_captures,
                                     error_message,
                                     code));
 }
 
 
-Handle<Object> RegExpImpl::JsreCompile(Handle<JSRegExp> re) {
+Handle<Object> RegExpImpl::JscreCompile(Handle<JSRegExp> re) {
   ASSERT_EQ(re->TypeTag(), JSRegExp::JSCRE);
   ASSERT(re->DataAt(JSRegExp::kJscreDataIndex)->IsUndefined());
 
   Handle<String> pattern(re->Pattern());
   JSRegExp::Flags flags = re->GetFlags();
 
   Handle<String> two_byte_pattern = StringToTwoByte(pattern);
 
   unsigned number_of_captures;
   const char* error_message = NULL;
@@ skipping 16 matching lines @@
     Handle<Object> regexp_err =
         Factory::NewSyntaxError("malformed_regexp", array);
     Top::Throw(*regexp_err);
     return Handle<Object>();
   }
 
   // Convert the return address to a ByteArray pointer.
   Handle<ByteArray> internal(
       ByteArray::FromDataStartAddress(reinterpret_cast<Address>(code)));
 
-  Handle<FixedArray> value = Factory::NewFixedArray(2);
-  value->set(CAPTURE_INDEX, Smi::FromInt(number_of_captures));
-  value->set(INTERNAL_INDEX, *internal);
+  Handle<FixedArray> value = Factory::NewFixedArray(kJscreDataLength);
+  value->set(kJscreNumberOfCapturesIndex, Smi::FromInt(number_of_captures));
+  value->set(kJscreInternalIndex, *internal);
   Factory::SetRegExpData(re, JSRegExp::JSCRE, pattern, flags, value);
 
   return re;
 }
 
 
-Handle<Object> RegExpImpl::JsreExecOnce(Handle<JSRegExp> regexp,
+Handle<Object> RegExpImpl::Re2kExecOnce(Handle<JSRegExp> regexp,
                                         int num_captures,
                                         Handle<String> subject,
                                         int previous_index,
                                         const uc16* two_byte_subject,
                                         int* offsets_vector,
                                         int offsets_vector_length) {
+  bool rc;
+  {
+    for (int i = (num_captures + 1) * 2 - 1; i >= 0; i--) {
+      offsets_vector[i] = -1;
+    }
+
+    AssertNoAllocation a;
+
+    LOG(RegExpExecEvent(regexp, previous_index, subject));
+
+    Handle<ByteArray> byte_codes = Re2kCode(regexp);
+
+    rc = Re2kInterpreter::Match(byte_codes,
+                                subject,
+                                offsets_vector,
+                                previous_index);
+  }
+
+  if (!rc) {
+    return Factory::null_value();
+  }
+
+  Handle<FixedArray> array = Factory::NewFixedArray(2 * (num_captures+1));
+  // The captures come in (start, end+1) pairs.
+  for (int i = 0; i < 2 * (num_captures+1); i += 2) {
+    array->set(i, Smi::FromInt(offsets_vector[i]));
+    array->set(i+1, Smi::FromInt(offsets_vector[i+1]));
+  }
+  return Factory::NewJSArrayWithElements(array);
+}
+
+
+Handle<Object> RegExpImpl::JscreExecOnce(Handle<JSRegExp> regexp,
+                                         int num_captures,
+                                         Handle<String> subject,
+                                         int previous_index,
+                                         const uc16* two_byte_subject,
+                                         int* offsets_vector,
+                                         int offsets_vector_length) {
   int rc;
   {
     AssertNoAllocation a;
-    ByteArray* internal = JsreInternal(regexp);
+    ByteArray* internal = JscreInternal(regexp);
     const JscreRegExp* js_regexp =
         reinterpret_cast<JscreRegExp*>(internal->GetDataStartAddress());
 
     LOG(RegExpExecEvent(regexp, previous_index, subject));
 
     rc = jsRegExpExecute(js_regexp,
                          two_byte_subject,
                          subject->length(),
                          previous_index,
                          offsets_vector,
@@ skipping 13 matching lines @@
     Handle<Object> code(Smi::FromInt(rc));
     Handle<Object> args[2] = { Factory::LookupAsciiSymbol("jsre_exec"), code };
     Handle<Object> regexp_err(
         Factory::NewTypeError("jsre_error", HandleVector(args, 2)));
     return Handle<Object>(Top::Throw(*regexp_err));
   }
 
   Handle<FixedArray> array = Factory::NewFixedArray(2 * (num_captures+1));
   // The captures come in (start, end+1) pairs.
   for (int i = 0; i < 2 * (num_captures+1); i += 2) {
-    array->set(i,
-               Smi::FromInt(offsets_vector[i]),
-               SKIP_WRITE_BARRIER);
-    array->set(i+1,
-               Smi::FromInt(offsets_vector[i+1]),
-               SKIP_WRITE_BARRIER);
+    array->set(i, Smi::FromInt(offsets_vector[i]));
+    array->set(i+1, Smi::FromInt(offsets_vector[i+1]));
   }
   return Factory::NewJSArrayWithElements(array);
 }
 
 
 class OffsetsVector {
  public:
-  inline OffsetsVector(int num_captures) {
-    offsets_vector_length_ = (num_captures + 1) * 3;
+  inline OffsetsVector(int num_registers) :
+    offsets_vector_length_(num_registers) {
     if (offsets_vector_length_ > kStaticOffsetsVectorSize) {
       vector_ = NewArray<int>(offsets_vector_length_);
     } else {
       vector_ = static_offsets_vector_;
     }
   }
 
 
   inline ~OffsetsVector() {
     if (offsets_vector_length_ > kStaticOffsetsVectorSize) {
       DeleteArray(vector_);
       vector_ = NULL;
     }
   }
 
 
   inline int* vector() {
     return vector_;
   }
 
 
   inline int length() {
     return offsets_vector_length_;
   }
 
  private:
   int* vector_;
   int offsets_vector_length_;
-  static const int kStaticOffsetsVectorSize = 30;
+  static const int kStaticOffsetsVectorSize = 50;
   static int static_offsets_vector_[kStaticOffsetsVectorSize];
 };
 
 
 int OffsetsVector::static_offsets_vector_[
     OffsetsVector::kStaticOffsetsVectorSize];
 
 
-Handle<Object> RegExpImpl::JsreExec(Handle<JSRegExp> regexp,
+Handle<Object> RegExpImpl::Re2kExec(Handle<JSRegExp> regexp,
                                     Handle<String> subject,
                                     Handle<Object> index) {
+  ASSERT_EQ(regexp->TypeTag(), JSRegExp::RE2K);
+  ASSERT(!regexp->DataAt(JSRegExp::kRe2kDataIndex)->IsUndefined());
+
+  // Prepare space for the return values.
+  int number_of_registers = Re2kNumberOfRegisters(regexp);
+  OffsetsVector offsets(number_of_registers);
+
+  int num_captures = Re2kNumberOfCaptures(regexp);
+
+  int previous_index = static_cast<int>(DoubleToInteger(index->Number()));
+
+  Handle<String> subject16 = CachedStringToTwoByte(subject);
+
+  Handle<Object> result(Re2kExecOnce(regexp,
+                                     num_captures,
+                                     subject,
+                                     previous_index,
+                                     subject16->GetTwoByteData(),
+                                     offsets.vector(),
+                                     offsets.length()));
+  return result;
+}
+
+
+Handle<Object> RegExpImpl::JscreExec(Handle<JSRegExp> regexp,
+                                     Handle<String> subject,
+                                     Handle<Object> index) {
   ASSERT_EQ(regexp->TypeTag(), JSRegExp::JSCRE);
   if (regexp->DataAt(JSRegExp::kJscreDataIndex)->IsUndefined()) {
-    Handle<Object> compile_result = JsreCompile(regexp);
+    Handle<Object> compile_result = JscreCompile(regexp);
+    if (compile_result->IsException()) return compile_result;
+  }
+  ASSERT(regexp->DataAt(JSRegExp::kJscreDataIndex)->IsFixedArray());
+
+  int num_captures = JscreNumberOfCaptures(regexp);
+
+  OffsetsVector offsets((num_captures + 1) * 3);
+
+  int previous_index = static_cast<int>(DoubleToInteger(index->Number()));
+
+  Handle<String> subject16 = CachedStringToTwoByte(subject);
+
+  Handle<Object> result(JscreExecOnce(regexp,
+                                      num_captures,
+                                      subject,
+                                      previous_index,
+                                      subject16->GetTwoByteData(),
+                                      offsets.vector(),
+                                      offsets.length()));
+
+  return result;
+}
+
+
+Handle<Object> RegExpImpl::Re2kExecGlobal(Handle<JSRegExp> regexp,
+                                          Handle<String> subject) {
+  ASSERT_EQ(regexp->TypeTag(), JSRegExp::RE2K);

[Lasse Reichstein, 2008/11/14 10:03:40]

This method looks like an almost, but not entirely, complete copy of
JsreExecGlobal. Could some of it be abstracted into one function?

+  ASSERT(!regexp->DataAt(JSRegExp::kRe2kDataIndex)->IsUndefined());
+
+  // Prepare space for the return values.
+  int number_of_registers = Re2kNumberOfRegisters(regexp);
+  OffsetsVector offsets(number_of_registers);
+
+  int previous_index = 0;
+
+  Handle<JSArray> result = Factory::NewJSArray(0);
+  int i = 0;
+  Handle<Object> matches;
+
+  Handle<String> subject16 = CachedStringToTwoByte(subject);
+
+  do {
+    if (previous_index > subject->length() || previous_index < 0) {
+      // Per ECMA-262 15.10.6.2, if the previous index is greater than the
+      // string length, there is no match.
+      matches = Factory::null_value();
+    } else {
+      matches = Re2kExecOnce(regexp,
+                             Re2kNumberOfCaptures(regexp),
+                             subject,
+                             previous_index,
+                             subject16->GetTwoByteData(),
+                             offsets.vector(),
+                             offsets.length());
+
+      if (matches->IsJSArray()) {
+        SetElement(result, i, matches);
+        i++;
+        previous_index = offsets.vector()[1];
+        if (offsets.vector()[0] == offsets.vector()[1]) {
+          previous_index++;
+        }
+      }
+    }
+  } while (matches->IsJSArray());
+
+  // If we exited the loop with an exception, throw it.
+  if (matches->IsNull()) {  // Exited loop normally.
+    return result;
+  } else {  // Exited loop with the exception in matches.
+    return matches;
+  }
+}
+
+
+Handle<Object> RegExpImpl::JscreExecGlobal(Handle<JSRegExp> regexp,
+                                           Handle<String> subject) {
+  ASSERT_EQ(regexp->TypeTag(), JSRegExp::JSCRE);
+  if (regexp->DataAt(JSRegExp::kJscreDataIndex)->IsUndefined()) {
+    Handle<Object> compile_result = JscreCompile(regexp);
     if (compile_result->IsException()) return compile_result;
   }
   ASSERT(regexp->DataAt(JSRegExp::kJscreDataIndex)->IsFixedArray());
 
   // Prepare space for the return values.
-  int num_captures = JsreCapture(regexp);
+  int num_captures = JscreNumberOfCaptures(regexp);
 
-  OffsetsVector offsets(num_captures);
-
-  int previous_index = static_cast<int>(DoubleToInteger(index->Number()));
-
-  Handle<String> subject16 = CachedStringToTwoByte(subject);
-
-  Handle<Object> result(JsreExecOnce(regexp, num_captures, subject,
-                                     previous_index,
-                                     subject16->GetTwoByteData(),
-                                     offsets.vector(), offsets.length()));
-
-  return result;
-}
-
-
-Handle<Object> RegExpImpl::JsreExecGlobal(Handle<JSRegExp> regexp,
-                                          Handle<String> subject) {
-  ASSERT_EQ(regexp->TypeTag(), JSRegExp::JSCRE);
-  if (regexp->DataAt(JSRegExp::kJscreDataIndex)->IsUndefined()) {
-    Handle<Object> compile_result = JsreCompile(regexp);
-    if (compile_result->IsException()) return compile_result;
-  }
-  ASSERT(regexp->DataAt(JSRegExp::kJscreDataIndex)->IsFixedArray());
-
-  // Prepare space for the return values.
-  int num_captures = JsreCapture(regexp);
-
-  OffsetsVector offsets(num_captures);
+  OffsetsVector offsets((num_captures + 1) * 3);
 
   int previous_index = 0;
 
   Handle<JSArray> result = Factory::NewJSArray(0);
   int i = 0;
   Handle<Object> matches;
 
   Handle<String> subject16 = CachedStringToTwoByte(subject);
 
   do {
     if (previous_index > subject->length() || previous_index < 0) {
       // Per ECMA-262 15.10.6.2, if the previous index is greater than the
       // string length, there is no match.
       matches = Factory::null_value();
     } else {
-      matches = JsreExecOnce(regexp, num_captures, subject, previous_index,
-                             subject16->GetTwoByteData(),
-                             offsets.vector(), offsets.length());
+      matches = JscreExecOnce(regexp,
+                              num_captures,
+                              subject,
+                              previous_index,
+                              subject16->GetTwoByteData(),
+                              offsets.vector(),
+                              offsets.length());
 
       if (matches->IsJSArray()) {
         SetElement(result, i, matches);
         i++;
         previous_index = offsets.vector()[1];
         if (offsets.vector()[0] == offsets.vector()[1]) {
           previous_index++;
         }
       }
     }
   } while (matches->IsJSArray());
 
   // If we exited the loop with an exception, throw it.
   if (matches->IsNull()) {  // Exited loop normally.
     return result;
   } else {  // Exited loop with the exception in matches.
     return matches;
   }
 }
 
 
-int RegExpImpl::JsreCapture(Handle<JSRegExp> re) {
+int RegExpImpl::JscreNumberOfCaptures(Handle<JSRegExp> re) {
   FixedArray* value = FixedArray::cast(re->DataAt(JSRegExp::kJscreDataIndex));
-  return Smi::cast(value->get(CAPTURE_INDEX))->value();
+  return Smi::cast(value->get(kJscreNumberOfCapturesIndex))->
+      value();
 }
 
 
-ByteArray* RegExpImpl::JsreInternal(Handle<JSRegExp> re) {
+ByteArray* RegExpImpl::JscreInternal(Handle<JSRegExp> re) {
   FixedArray* value = FixedArray::cast(re->DataAt(JSRegExp::kJscreDataIndex));
-  return ByteArray::cast(value->get(INTERNAL_INDEX));
+  return ByteArray::cast(value->get(kJscreInternalIndex));
+}
+
+
+int RegExpImpl::Re2kNumberOfCaptures(Handle<JSRegExp> re) {
+  FixedArray* value = FixedArray::cast(re->DataAt(JSRegExp::kRe2kDataIndex));
+  return Smi::cast(value->get(kRe2kNumberOfCapturesIndex))->value();
+}
+
+
+int RegExpImpl::Re2kNumberOfRegisters(Handle<JSRegExp> re) {
+  FixedArray* value = FixedArray::cast(re->DataAt(JSRegExp::kRe2kDataIndex));
+  return Smi::cast(value->get(kRe2kNumberOfRegistersIndex))->value();
+}
+
+
+Handle<ByteArray> RegExpImpl::Re2kCode(Handle<JSRegExp> re) {
+  FixedArray* value = FixedArray::cast(re->DataAt(JSRegExp::kRe2kDataIndex));
+  return Handle<ByteArray>(ByteArray::cast(value->get(kRe2kCodeIndex)));
 }
 
 
 // -------------------------------------------------------------------
 // New regular expression engine
 
 
 class DotPrinter;
 
 
 class RegExpCompiler {
  public:
   explicit RegExpCompiler(int capture_count)
     : next_register_(2 * capture_count),
       work_list_(NULL) { }
 
   int AllocateRegister() { return next_register_++; }
 
   Handle<FixedArray> Assemble(RegExpMacroAssembler* assembler,
-                              RegExpNode* start);
+                              RegExpNode* start,
+                              int capture_count);
 
   inline void AddWork(RegExpNode* node) { work_list_->Add(node); }
 
-  static const int kImplementationOffset = 0;
-  static const int kNumberOfRegistersOffset = 0;
-  static const int kCodeOffset = 1;
-
   RegExpMacroAssembler* macro_assembler() {
     return macro_assembler_;
   }
  private:
   int next_register_;
   List<RegExpNode*>* work_list_;
   RegExpMacroAssembler* macro_assembler_;
 };
 
 
+// Attempts to compile the regexp using a Regexp2000 code generator.  Returns
+// a fixed array or a null handle depending on whether it succeeded.
 Handle<FixedArray> RegExpCompiler::Assemble(
     RegExpMacroAssembler* macro_assembler,
-    RegExpNode* start) {
+    RegExpNode* start,
+    int capture_count) {

[Lasse Reichstein, 2008/11/14 10:03:40]

Also need to know if we ignore case.

   macro_assembler_ = macro_assembler;
   List <RegExpNode*> work_list(0);
   work_list_ = &work_list;
-  start->GoTo(this);
+  Label fail;
+  macro_assembler->PushBacktrack(&fail);
+  if (!start->GoTo(this)) {
+    fail.Unuse();
+    return Handle<FixedArray>::null();
+  }
   while (!work_list.is_empty()) {
-    work_list.RemoveLast()->Emit(this);
+    if (!work_list.RemoveLast()->Emit(this)) {
+      fail.Unuse();
+      return Handle<FixedArray>::null();
+    }
   }
-  Handle<FixedArray> array = Factory::NewFixedArray(3);
-  array->set(kImplementationOffset,
-             Smi::FromInt(macro_assembler->Implementation()),
-             SKIP_WRITE_BARRIER);
-  array->set(kNumberOfRegistersOffset,
-             Smi::FromInt(next_register_),
-             SKIP_WRITE_BARRIER);
+  macro_assembler->Bind(&fail);
+  macro_assembler->Fail();
+  Handle<FixedArray> array =
+      Factory::NewFixedArray(RegExpImpl::kRe2kDataLength);
+  array->set(RegExpImpl::kRe2kImplementationIndex,
+             Smi::FromInt(macro_assembler->Implementation()));
+  array->set(RegExpImpl::kRe2kNumberOfRegistersIndex,
+             Smi::FromInt(next_register_));
+  array->set(RegExpImpl::kRe2kNumberOfCapturesIndex,
+             Smi::FromInt(capture_count));
   Handle<Object> code = macro_assembler->GetCode();
+  array->set(RegExpImpl::kRe2kCodeIndex, *code);
   work_list_ = NULL;
   return array;
 }
 
 
-void RegExpNode::GoTo(RegExpCompiler* compiler) {
+bool RegExpNode::GoTo(RegExpCompiler* compiler) {
   if (label.is_bound()) {
     compiler->macro_assembler()->GoTo(&label);
+    return true;
   } else {
-    Emit(compiler);
+    return Emit(compiler);
   }
 }
 
 
 void RegExpNode::EmitAddress(RegExpCompiler* compiler) {
   compiler->macro_assembler()->EmitOrLink(&label);
 }
 
 
 EndNode EndNode::kAccept(ACCEPT);
 EndNode EndNode::kBacktrack(BACKTRACK);
 
 
+bool EndNode::Emit(RegExpCompiler* compiler) {
+  switch (action_) {
+    case ACCEPT:
+      compiler->macro_assembler()->Succeed();
+      return true;
+    case BACKTRACK:
+      compiler->macro_assembler()->Backtrack();
+      return true;
+  }
+  return false;
+}
+
+
 void GuardedAlternative::AddGuard(Guard* guard) {
   if (guards_ == NULL)
     guards_ = new ZoneList<Guard*>(1);
   guards_->Add(guard);
 }
 
 
 ActionNode* ActionNode::StoreRegister(int reg,
                                       int val,
                                       RegExpNode* on_success) {
@@ skipping 55 matching lines @@
     visitor->Visit##Type(this);                                      \
   }
 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
 #undef DEFINE_ACCEPT
 
 
 // -------------------------------------------------------------------
 // Emit code.
 
 
-void ChoiceNode::Emit(RegExpCompiler* compiler) {
+bool ChoiceNode::Emit(RegExpCompiler* compiler) {
   // TODO(erikcorry): Implement this.
-  UNREACHABLE();
+  return false;
 }
 
 
-void ActionNode::Emit(RegExpCompiler* compiler) {
+bool ActionNode::Emit(RegExpCompiler* compiler) {
   RegExpMacroAssembler* macro = compiler->macro_assembler();
   switch (type_) {
     case STORE_REGISTER:
       macro->SetRegister(data_.u_store_register.reg,
                          data_.u_store_register.value);
       break;
     case INCREMENT_REGISTER:
       macro->AdvanceRegister(data_.u_increment_register.reg, 1);
       break;
     case STORE_POSITION:
       macro->PushCurrentPosition();
       break;
     case RESTORE_POSITION:
       macro->PopCurrentPosition();
       break;
     case BEGIN_SUBMATCH:
       // TODO(erikcorry): Implement this.
-      UNREACHABLE();
-      break;
+      return false;
     case ESCAPE_SUBMATCH:
       // TODO(erikcorry): Implement this.
-      UNREACHABLE();
-      break;
+      return false;
     case END_SUBMATCH:
       // TODO(erikcorry): Implement this.
+      return false;
+    default:
       UNREACHABLE();
-      break;
+      return false;
   }
+  compiler->AddWork(on_success());
+  return true;
 }
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
 
 
 #ifdef DEBUG
 
 
@@ skipping 773 matching lines @@
   outgoing.set_table(NULL);
   outgoing.Analyze(that->on_success());
 }
 
 
 void Analysis::VisitAction(ActionNode* that) {
   Analyze(that->on_success());
 }
 
 
-RegExpNode* RegExpEngine::Compile(RegExpParseResult* input) {
+Handle<FixedArray> RegExpEngine::Compile(RegExpParseResult* input,
+                                         RegExpNode** node_return) {
   RegExpCompiler compiler(input->capture_count);
   // Wrap the body of the regexp in capture #0.
   RegExpNode* captured_body = RegExpCapture::ToNode(input->tree,
                                                     0,
                                                     &compiler,
                                                     EndNode::GetAccept(),
                                                     EndNode::GetBacktrack());
   // Add a .*? at the beginning, outside the body capture.
   // Note: We could choose to not add this if the regexp is anchored at
   //   the start of the input but I'm not sure how best to do that and
   //   since we don't even handle ^ yet I'm saving that optimization for
   //   later.
   RegExpNode* node = RegExpQuantifier::ToNode(0,
                                               RegExpQuantifier::kInfinity,
                                               false,
                                               new RegExpCharacterClass('.'),
                                               &compiler,
                                               captured_body,
                                               EndNode::GetBacktrack());
+  if (node_return != NULL) *node_return = node;
   Analysis analysis(&compiler);
   analysis.Analyze(node);
-  return node;
+  byte codes[10240];
+  Re2kAssembler assembler(Vector<byte>(codes, 1024));
+  RegExpMacroAssemblerRe2k macro_assembler(&assembler);
+  return compiler.Assemble(&macro_assembler, node, input->capture_count);
 }
 
 
 RegExpMacroAssembler::~RegExpMacroAssembler() {
 }
 
 
 }}  // namespace v8::internal