* No failures on our own tests....

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 442 matching lines @@
   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::Re2kExecOnce(Handle<JSRegExp> regexp,
                                         int num_captures,
-                                        Handle<String> subject,
+                                        Handle<String> two_byte_subject,
                                         int previous_index,
-                                        const uc16* two_byte_subject,
                                         int* offsets_vector,
                                         int offsets_vector_length) {
+#ifdef DEBUG
+  if (FLAG_trace_regexp_bytecodes) {
+    String* pattern = regexp->Pattern();
+    PrintF("\n\nRegexp match:   /%s/\n\n", *(pattern->ToCString()));
+    PrintF("\n\nSubject string: '%s'\n\n", *(two_byte_subject->ToCString()));
+  }
+#endif
+  ASSERT(StringShape(*two_byte_subject).IsTwoByteRepresentation());
+  ASSERT(two_byte_subject->IsFlat(StringShape(*two_byte_subject)));
   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));
+    LOG(RegExpExecEvent(regexp, previous_index, two_byte_subject));
 
     Handle<ByteArray> byte_codes = Re2kCode(regexp);
 
     rc = Re2kInterpreter::Match(byte_codes,
-                                subject,
+                                two_byte_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.
@@ skipping 106 matching lines @@
   // 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()));
+  Handle<Object> result(
+      Re2kExecOnce(regexp,
+                   num_captures,
+                   subject16,
+                   previous_index,
+                   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 = JscreCompile(regexp);
@@ skipping 39 matching lines @@
   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,
+                             subject16,
                              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++;
         }
@@ skipping 151 matching lines @@
   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_; }
   EndNode* accept() { return accept_; }
   EndNode* backtrack() { return backtrack_; }
 
+  static const int kMaxRecursion = 100;
+  inline int recursion_depth() { return recursion_depth_; }
+  inline void IncrementRecursionDepth() { recursion_depth_++; }
+  inline void DecrementRecursionDepth() { recursion_depth_--; }
+
  private:
   EndNode* accept_;
   EndNode* backtrack_;
   int next_register_;
   List<RegExpNode*>* work_list_;
+  int recursion_depth_;
   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.
 RegExpCompiler::RegExpCompiler(int capture_count)
-  : next_register_(2 * capture_count),
-    work_list_(NULL) {
+  : next_register_(2 * (capture_count + 1)),
+    work_list_(NULL),
+    recursion_depth_(0) {
   accept_ = new EndNode(EndNode::ACCEPT);
   backtrack_ = new EndNode(EndNode::BACKTRACK);
 }
 
 
 Handle<FixedArray> RegExpCompiler::Assemble(
     RegExpMacroAssembler* macro_assembler,
     RegExpNode* start,
     int capture_count,
     bool case_independent) {
   if (case_independent) return Handle<FixedArray>::null();
   macro_assembler_ = macro_assembler;
   List <RegExpNode*> work_list(0);
   work_list_ = &work_list;
   Label fail;
   macro_assembler->PushBacktrack(&fail);
   if (!start->GoTo(this)) {
     fail.Unuse();
     return Handle<FixedArray>::null();
   }
   while (!work_list.is_empty()) {
-    if (!work_list.RemoveLast()->Emit(this)) {
+    if (!work_list.RemoveLast()->GoTo(this)) {
       fail.Unuse();
       return Handle<FixedArray>::null();
     }
   }
   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;
 }
 
 
 bool RegExpNode::GoTo(RegExpCompiler* compiler) {
+  // TODO(erikcorry): Implement support.
+  if (info_.follows_word_interest ||
+      info_.follows_newline_interest ||
+      info_.follows_start_interest) {
+    return false;
+  }
   if (label_.is_bound()) {
     compiler->macro_assembler()->GoTo(&label_);
     return true;
   } else {
-    return Emit(compiler);
+    if (compiler->recursion_depth() > RegExpCompiler::kMaxRecursion) {
+      compiler->macro_assembler()->GoTo(&label_);
+      compiler->AddWork(this);
+      return true;
+    } else {
+      compiler->IncrementRecursionDepth();
+      bool how_it_went = Emit(compiler);
+      compiler->DecrementRecursionDepth();
+      return how_it_went;
+    }
   }
 }
 
 
+bool EndNode::GoTo(RegExpCompiler* compiler) {
+  if (info()->follows_word_interest ||
+      info()->follows_newline_interest ||
+      info()->follows_start_interest) {
+    return false;
+  }
+  if (!label()->is_bound()) {
+    Bind(compiler->macro_assembler());
+  }
+  switch (action_) {
+    case ACCEPT:
+      compiler->macro_assembler()->Succeed();
+    break;
+    case BACKTRACK:
+      compiler->macro_assembler()->Backtrack();
+    break;
+  }
+  return true;
+}
+
+
 Label* RegExpNode::label() {
   return &label_;
 }
 
 
 bool EndNode::Emit(RegExpCompiler* compiler) {
+  RegExpMacroAssembler* macro = compiler->macro_assembler();
   switch (action_) {
     case ACCEPT:
-      compiler->macro_assembler()->Succeed();
+      Bind(macro);
+      macro->Succeed();
       return true;
     case BACKTRACK:
-      compiler->macro_assembler()->Backtrack();
+      Bind(macro);
+      macro->Backtrack();
       return true;
   }
   return false;
 }
 
 
 void GuardedAlternative::AddGuard(Guard* guard) {
   if (guards_ == NULL)
     guards_ = new ZoneList<Guard*>(1);
   guards_->Add(guard);
@@ skipping 51 matching lines @@
     visitor->Visit##Type(this);                                      \
   }
 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
 #undef DEFINE_ACCEPT
 
 
 // -------------------------------------------------------------------
 // Emit code.
 
 
-void ChoiceNode::GenerateGuard(RegExpCompiler* compiler,
-                               Guard *guard,
+void ChoiceNode::GenerateGuard(RegExpMacroAssembler* macro_assembler,
+                               Guard* guard,
                                Label* on_failure) {
+  switch (guard->op()) {
+    case Guard::LT:
+      macro_assembler->IfRegisterGE(guard->reg(), guard->value(), on_failure);
+      break;
+    case Guard::GEQ:
+      macro_assembler->IfRegisterLT(guard->reg(), guard->value(), on_failure);
+      break;
+  }
+}
+
+
+bool TextNode::Emit(RegExpCompiler* compiler) {
+  RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
+  Bind(macro_assembler);
+  int element_count = elms_->length();
+  int cp_offset = 0;
+  for (int i = 0; i < element_count; i++) {
+    TextElement elm = (*elms_)[i];
+    switch (elm.type) {
+      case TextElement::ATOM: {
+        Vector<const uc16> quarks = elm.data.u_atom->data();
+        macro_assembler->CheckCharacters(quarks,
+                                         cp_offset,
+                                         on_failure_->label());
+        cp_offset += quarks.length();
+        break;
+      }
+      case TextElement::CHAR_CLASS: {
+        RegExpCharacterClass* cc = elm.data.u_char_class;
+        if (cc->is_negated()) return false;
+        macro_assembler->LoadCurrentCharacter(cp_offset, on_failure_->label());
+        cp_offset++;
+
+        ZoneList<CharacterRange>* ranges = cc->ranges();
+
+        Label found;
+
+        int range_count = ranges->length();
+
+        if (range_count == 0) {
+          on_failure()->GoTo(compiler);
+          break;
+        }
+
+        for (int i = 0; i < range_count - 1; i++) {
+          CharacterRange& range = (*ranges)[i];
+          Label next_range;
+          uc16 from = range.from();
+          uc16 to = range.to();
+          if (from != 0) {
+            macro_assembler->CheckCharacterLT(from, &next_range);
+          }
+          if (to != 0xffff) {
+            macro_assembler->CheckCharacterLT(to + 1, &found);
+          } else {
+            macro_assembler->AdvanceCurrentPosition(1);
+            on_success()->GoTo(compiler);
+          }
+          macro_assembler->Bind(&next_range);
+        }
+
+        CharacterRange& range = (*ranges)[range_count - 1];
+        uc16 from = range.from();
+        uc16 to = range.to();
+        if (from != 0) {
+          macro_assembler->CheckCharacterLT(from, on_failure_->label());
+        }
+        if (to != 0xffff) {
+          macro_assembler->CheckCharacterGT(to, on_failure_->label());
+        }
+        compiler->AddWork(on_failure_);
+        macro_assembler->Bind(&found);
+        break;
+      }
+      default:
+        UNREACHABLE();
+        return false;
+    }
+  }
+  macro_assembler->AdvanceCurrentPosition(cp_offset);
+  return on_success()->GoTo(compiler);
 }
 
 
 bool ChoiceNode::Emit(RegExpCompiler* compiler) {
   int choice_count = alternatives_->length();
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
+  Bind(macro_assembler);
   // For now we just call all choices one after the other.  The idea ultimately
   // is to use the Dispatch table to try only the relevant ones.
-  for (int i = 0; i < choice_count; i++) {
+  int i;
+  for (i = 0; i < choice_count - 1; i++) {
     GuardedAlternative alternative = (*alternatives_)[i];
     Label after;
-    Label* next_alternative;
-    if (i < choice_count - 1) {
-      next_alternative = &after;
-    } else {
-      next_alternative = on_failure_->label();
-    }
+    Label after_no_pop_cp;
     ZoneList<Guard*>* guards = alternative.guards();
     if (guards != NULL) {
       int guard_count = guards->length();
       for (int j = 0; j < guard_count; j++) {
-        GenerateGuard(compiler, (*guards)[i], next_alternative);
+        GenerateGuard(macro_assembler, (*guards)[j], &after_no_pop_cp);
       }
     }
-    macro_assembler->PushBacktrack(next_alternative);
-    if (!alternative.node()->Emit(compiler)) {
+    macro_assembler->PushCurrentPosition();
+    macro_assembler->PushBacktrack(&after);
+    if (!alternative.node()->GoTo(compiler)) {
       after.Unuse();
-      if (next_alternative != &after) {
-        next_alternative->Unuse();
-      }
+      after_no_pop_cp.Unuse();
       return false;
     }
-    if (i < choice_count - 1) {
-      macro_assembler->Bind(&after);
-    } else {
-      after.Unuse();
+    macro_assembler->Bind(&after);
+    macro_assembler->PopCurrentPosition();
+    macro_assembler->Bind(&after_no_pop_cp);
+  }
+  GuardedAlternative alternative = (*alternatives_)[i];
+  ZoneList<Guard*>* guards = alternative.guards();
+  if (guards != NULL) {
+    int guard_count = guards->length();
+    for (int j = 0; j < guard_count; j++) {
+      GenerateGuard(macro_assembler, (*guards)[j], on_failure_->label());
     }
   }
+  if (!on_failure_->IsBacktrack()) {
+    macro_assembler->PushBacktrack(on_failure_->label());
+  }
+  if (!alternative.node()->GoTo(compiler)) {
+    return false;
+  }
   compiler->AddWork(on_failure_);
   return true;
 }
 
 
 bool ActionNode::Emit(RegExpCompiler* compiler) {
   RegExpMacroAssembler* macro = compiler->macro_assembler();
+  Bind(macro);
   switch (type_) {
     case STORE_REGISTER:
       macro->SetRegister(data_.u_store_register.reg,
                          data_.u_store_register.value);
       break;
-    case INCREMENT_REGISTER:
+    case INCREMENT_REGISTER: {
+      Label undo;
+      macro->PushBacktrack(&undo);
       macro->AdvanceRegister(data_.u_increment_register.reg, 1);
+      bool ok = on_success()->GoTo(compiler);
+      if (!ok) {
+        undo.Unuse();
+        return false;
+      }
+      macro->Bind(&undo);
+      macro->AdvanceRegister(data_.u_increment_register.reg, -1);
+      macro->Backtrack();
       break;
-    case STORE_POSITION:
-      macro->PushCurrentPosition();
+    }
+    case STORE_POSITION: {
+      Label undo;
+      macro->PushRegister(data_.u_position_register.reg);
+      macro->PushBacktrack(&undo);
+      macro->WriteCurrentPositionToRegister(data_.u_position_register.reg);
+      bool ok = on_success()->GoTo(compiler);
+      if (!ok) {
+        undo.Unuse();
+        return false;
+      }
+      macro->Bind(&undo);
+      macro->PopRegister(data_.u_position_register.reg);
+      macro->Backtrack();
       break;
+    }
     case RESTORE_POSITION:
-      macro->PopCurrentPosition();
-      break;
+      // TODO(erikcorry): Implement this.
+      return false;
     case BEGIN_SUBMATCH:
       // TODO(erikcorry): Implement this.
       return false;
     case ESCAPE_SUBMATCH:
       // TODO(erikcorry): Implement this.
       return false;
     case END_SUBMATCH:
       // TODO(erikcorry): Implement this.
       return false;
     default:
       UNREACHABLE();
       return false;
   }
-  compiler->AddWork(on_success());
-  return true;
+  return on_success()->GoTo(compiler);
 }
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
 
 
 #ifdef DEBUG
 
 
@@ skipping 473 matching lines @@
   RegExpNode* current = on_success;
   for (int i = children->length() - 1; i >= 0; i--) {
     current = children->at(i)->ToNode(compiler, current, on_failure);
   }
   return current;
 }
 
 
 static const int kSpaceRangeCount = 20;
 static const uc16 kSpaceRanges[kSpaceRangeCount] = {
-  0x0009, 0x0009, 0x000B, 0x000C, 0x0020, 0x0020, 0x00A0, 0x00A0,
-  0x1680, 0x1680, 0x180E, 0x180E, 0x2000, 0x200A, 0x202F, 0x202F,
-  0x205F, 0x205F, 0x3000, 0x3000
+  0x0009, 0x000D, 0x0020, 0x0020, 0x00A0, 0x00A0, 0x1680,
+  0x1680, 0x180E, 0x180E, 0x2000, 0x200A, 0x2028, 0x2029,
+  0x202F, 0x202F, 0x205F, 0x205F, 0x3000, 0x3000
 };
 
 
 static const int kWordRangeCount = 8;
 static const uc16 kWordRanges[kWordRangeCount] = {
   '0', '9', 'A', 'Z', '_', '_', 'a', 'z'
 };
 
 
 static const int kDigitRangeCount = 2;
@@ skipping 381 matching lines @@
     DispatchTableConstructor constructor(node->table());
     constructor.BuildTable(node);
   }
   ASSERT(node->table_calculated());
   AddDispatchRange adder(this);
   node->table()->ForEach(&adder);
 }
 
 
 void DispatchTableConstructor::VisitBackreference(BackreferenceNode* that) {
-  UNIMPLEMENTED();
+  // TODO(plesner): What should this do?
 }
 
 
 
 static int CompareRangeByFrom(const CharacterRange* a,
                               const CharacterRange* b) {
   return Spaceship<uc16>(a->from(), b->from());
 }
 
 
@@ skipping 65 matching lines @@
   RegExpNode* node = RegExpQuantifier::ToNode(0,
                                               RegExpQuantifier::kInfinity,
                                               false,
                                               new RegExpCharacterClass('.'),
                                               &compiler,
                                               captured_body,
                                               compiler.backtrack());
   if (node_return != NULL) *node_return = node;
   Analysis analysis;
   analysis.EnsureAnalyzed(node);
-  byte codes[10240];
+  byte codes[1024];
   Re2kAssembler assembler(Vector<byte>(codes, 1024));
   RegExpMacroAssemblerRe2k macro_assembler(&assembler);
   return compiler.Assemble(&macro_assembler,
                            node,
                            input->capture_count,
                            ignore_case);
 }
 
 RegExpMacroAssembler::RegExpMacroAssembler() {
 }
 
 RegExpMacroAssembler::~RegExpMacroAssembler() {
 }
 
 
 }}  // namespace v8::internal