Bring toiger up to date with bleeding edge 984.

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 242 matching lines @@
   bool in_cache = !cached.is_null();
   LOG(RegExpCompileEvent(re, in_cache));
 
   Handle<Object> result;
   if (in_cache) {
     re->set_data(*cached);
     result = re;
   } else {
     FlattenString(pattern);
     ZoneScope zone_scope(DELETE_ON_EXIT);
-    RegExpParseResult parse_result;
+    RegExpCompileData parse_result;
     FlatStringReader reader(pattern);
     if (!ParseRegExp(&reader, flags.is_multiline(), &parse_result)) {
       // Throw an exception if we fail to parse the pattern.
       ThrowRegExpException(re,
                            pattern,
                            parse_result.error,
                            "malformed_regexp");
       return Handle<Object>::null();
     }
-    RegExpAtom* atom = parse_result.tree->AsAtom();
-    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);
-      }
+
+    if (parse_result.simple && !flags.is_ignore_case()) {
+      // Parse-tree is a single atom that is equal to the pattern.
+      result = AtomCompile(re, pattern, flags, pattern);
+    } else if (parse_result.tree->IsAtom() &&
+        !flags.is_ignore_case() &&
+        parse_result.capture_count == 0) {
+      // TODO(lrn) Accept capture_count > 0 on atoms.
+      RegExpAtom* atom = parse_result.tree->AsAtom();
+      Vector<const uc16> atom_pattern = atom->data();
+      Handle<String> atom_string =
+          Factory::NewStringFromTwoByte(atom_pattern);
+      result = AtomCompile(re, pattern, flags, atom_string);
+    } else if (FLAG_irregexp) {
+      result = IrregexpPrepare(re, pattern, flags);
     } else {
-      if (FLAG_irregexp) {
-        result = IrregexpPrepare(re, pattern, flags);
-      } else {
-        result = JscrePrepare(re, pattern, flags);
-      }
+      result = JscrePrepare(re, pattern, flags);
     }
     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);
     }
   }
 
   return result;
 }
 
 
 Handle<Object> RegExpImpl::Exec(Handle<JSRegExp> regexp,
                                 Handle<String> subject,
                                 Handle<Object> index) {
   switch (regexp->TypeTag()) {
     case JSRegExp::ATOM:
       return AtomExec(regexp, subject, index);
     case JSRegExp::IRREGEXP: {
       Handle<Object> result = IrregexpExec(regexp, subject, index);
-      if (!result.is_null()) {
+      if (!result.is_null() || Top::has_pending_exception()) {
         return result;
       }
       // We couldn't handle the regexp using Irregexp, so fall back
       // on JSCRE.
       // Reset the JSRegExp to use JSCRE.
       JscrePrepare(regexp,
                    Handle<String>(regexp->Pattern()),
                    regexp->GetFlags());
       // Fall-through to JSCRE.
     }
     case JSRegExp::JSCRE:
       if (FLAG_disable_jscre) {
         UNIMPLEMENTED();
       }
       return JscreExec(regexp, subject, index);
     default:
       UNREACHABLE();
       return Handle<Object>::null();
   }
 }
 
 
 Handle<Object> RegExpImpl::ExecGlobal(Handle<JSRegExp> regexp,
                                 Handle<String> subject) {
   switch (regexp->TypeTag()) {
     case JSRegExp::ATOM:
       return AtomExecGlobal(regexp, subject);
     case JSRegExp::IRREGEXP: {
       Handle<Object> result = IrregexpExecGlobal(regexp, subject);
-      if (!result.is_null()) {
+      if (!result.is_null() || Top::has_pending_exception()) {
         return result;
       }
-      // We couldn't handle the regexp using Irregexp, so fall back
-      // on JSCRE.
-      // Reset the JSRegExp to use JSCRE.
+      // Empty handle as result but no exception thrown means that
+      // the regexp contains features not yet handled by the irregexp
+      // compiler.
+      // We have to fall back on JSCRE. Reset the JSRegExp to use JSCRE.
       JscrePrepare(regexp,
                    Handle<String>(regexp->Pattern()),
                    regexp->GetFlags());
       // Fall-through to JSCRE.
     }
     case JSRegExp::JSCRE:
       if (FLAG_disable_jscre) {
         UNIMPLEMENTED();
       }
       return JscreExecGlobal(regexp, subject);
@@ skipping 318 matching lines @@
   } else {
     // Exited loop with the exception in matches.
     return matches;
   }
 }
 
 
 // Irregexp implementation.
 
 
+// Retrieves a compiled version of the regexp for either ASCII or non-ASCII
+// strings. If the compiled version doesn't already exist, it is compiled
+// from the source pattern.
+// Irregexp is not feature complete yet. If there is something in the
+// regexp that the compiler cannot currently handle, an empty
+// handle is returned, but no exception is thrown.
 static Handle<FixedArray> GetCompiledIrregexp(Handle<JSRegExp> re,
                                               bool is_ascii) {
   ASSERT(re->DataAt(JSRegExp::kIrregexpDataIndex)->IsFixedArray());
   Handle<FixedArray> alternatives(
       FixedArray::cast(re->DataAt(JSRegExp::kIrregexpDataIndex)));
   ASSERT_EQ(2, alternatives->length());
 
   int index = is_ascii ? 0 : 1;
   Object* entry = alternatives->get(index);
   if (!entry->IsNull()) {
     return Handle<FixedArray>(FixedArray::cast(entry));
   }
 
   // Compile the RegExp.
   ZoneScope zone_scope(DELETE_ON_EXIT);
 
   JSRegExp::Flags flags = re->GetFlags();
 
   Handle<String> pattern(re->Pattern());
   StringShape shape(*pattern);
   if (!pattern->IsFlat(shape)) {
     pattern->Flatten(shape);
   }
 
-  RegExpParseResult parse_result;
+  RegExpCompileData compile_data;
   FlatStringReader reader(pattern);
-  if (!ParseRegExp(&reader, flags.is_multiline(), &parse_result)) {
+  if (!ParseRegExp(&reader, flags.is_multiline(), &compile_data)) {
     // Throw an exception if we fail to parse the pattern.
     // THIS SHOULD NOT HAPPEN. We already parsed it successfully once.
     ThrowRegExpException(re,
                          pattern,
-                         parse_result.error,
+                         compile_data.error,
                          "malformed_regexp");
     return Handle<FixedArray>::null();
   }
   Handle<FixedArray> compiled_entry =
-      RegExpEngine::Compile(&parse_result,
-                            NULL,
+      RegExpEngine::Compile(&compile_data,
                             flags.is_ignore_case(),
                             flags.is_multiline(),
                             pattern,
                             is_ascii);
   if (!compiled_entry.is_null()) {
     alternatives->set(index, *compiled_entry);
   }
   return compiled_entry;
 }
 
@@ skipping 172 matching lines @@
         start_offset += slice->start();
         end_offset += slice->start();
         subject = Handle<String>(slice->buffer());
       }
 
       // String is now either Sequential or External
       StringShape flatshape(*subject);
       bool is_ascii = flatshape.IsAsciiRepresentation();
       int char_size_shift = is_ascii ? 0 : 1;
 
+      RegExpMacroAssemblerIA32::Result res;
+
       if (flatshape.IsExternal()) {
         const byte* address;
         if (is_ascii) {
           ExternalAsciiString* ext = ExternalAsciiString::cast(*subject);
           address = reinterpret_cast<const byte*>(ext->resource()->data());
         } else {
           ExternalTwoByteString* ext = ExternalTwoByteString::cast(*subject);
           address = reinterpret_cast<const byte*>(ext->resource()->data());
         }
-        rc = RegExpMacroAssemblerIA32::Execute(
+        res = RegExpMacroAssemblerIA32::Execute(
             *code,
             &address,
             start_offset << char_size_shift,
             end_offset << char_size_shift,
             offsets_vector,
             previous_index == 0);
       } else {  // Sequential string
         Address char_address =
             is_ascii ? SeqAsciiString::cast(*subject)->GetCharsAddress()
                      : SeqTwoByteString::cast(*subject)->GetCharsAddress();
         int byte_offset = char_address - reinterpret_cast<Address>(*subject);
-        rc = RegExpMacroAssemblerIA32::Execute(
+        res = RegExpMacroAssemblerIA32::Execute(
             *code,
             subject.location(),
             byte_offset + (start_offset << char_size_shift),
             byte_offset + (end_offset << char_size_shift),
             offsets_vector,
             previous_index == 0);
       }
 
+      if (res == RegExpMacroAssemblerIA32::EXCEPTION) {
+        ASSERT(Top::has_pending_exception());
+        return Handle<Object>::null();
+      }
+      rc = (res == RegExpMacroAssemblerIA32::SUCCESS);
+
       if (rc) {
         // Capture values are relative to start_offset only.
         for (int i = 0; i < offsets_vector_length; i++) {
           if (offsets_vector[i] >= 0) {
             offsets_vector[i] += previous_index;
           }
         }
       }
       break;
 #else
@@ skipping 1641 matching lines @@
 
 
 RegExpNode* RegExpText::ToNode(RegExpCompiler* compiler,
                                RegExpNode* on_success) {
   return new TextNode(elements(), on_success);
 }
 
 
 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler,
                                          RegExpNode* on_success) {
-  ZoneList<TextElement>* elms = new ZoneList<TextElement>(1);
-  elms->Add(TextElement::CharClass(this));
-  return new TextNode(elms, on_success);
+  return new TextNode(this, on_success);
 }
 
 
 RegExpNode* RegExpDisjunction::ToNode(RegExpCompiler* compiler,
                                       RegExpNode* on_success) {
   ZoneList<RegExpTree*>* alternatives = this->alternatives();
   int length = alternatives->length();
   ChoiceNode* result = new ChoiceNode(length);
   for (int i = 0; i < length; i++) {
     GuardedAlternative alternative(alternatives->at(i)->ToNode(compiler,
@@ skipping 639 matching lines @@
     return entry->out_set();
   else
     return empty();
 }
 
 
 // -------------------------------------------------------------------
 // Analysis
 
 
-void Analysis::EnsureAnalyzed(RegExpNode* that) {
+void AssertionPropagation::EnsureAnalyzed(RegExpNode* that) {
   if (that->info()->been_analyzed || that->info()->being_analyzed)
     return;
   that->info()->being_analyzed = true;
   that->Accept(this);
   that->info()->being_analyzed = false;
   that->info()->been_analyzed = true;
 }
 
 
-void Analysis::VisitEnd(EndNode* that) {
+void AssertionPropagation::VisitEnd(EndNode* that) {
   // nothing to do
 }
 
 
 void TextNode::CalculateOffsets() {
   int element_count = elements()->length();
   // Set up the offsets of the elements relative to the start.  This is a fixed
   // quantity since a TextNode can only contain fixed-width things.
   int cp_offset = 0;
   for (int i = 0; i < element_count; i++) {
     TextElement& elm = elements()->at(i);
     elm.cp_offset = cp_offset;
     if (elm.type == TextElement::ATOM) {
       cp_offset += elm.data.u_atom->data().length();
     } else {
       cp_offset++;
       Vector<const uc16> quarks = elm.data.u_atom->data();
     }
   }
 }
 
 
-void Analysis::VisitText(TextNode* that) {
+void AssertionPropagation::VisitText(TextNode* that) {
   if (ignore_case_) {
     that->MakeCaseIndependent();
   }
   EnsureAnalyzed(that->on_success());
   NodeInfo* info = that->info();
   NodeInfo* next_info = that->on_success()->info();
   // If the following node is interested in what it follows then this
   // node must determine it.
   info->determine_newline = next_info->follows_newline_interest;
   info->determine_word = next_info->follows_word_interest;
   info->determine_start = next_info->follows_start_interest;
   that->CalculateOffsets();
 }
 
 
-void Analysis::VisitAction(ActionNode* that) {
+void AssertionPropagation::VisitAction(ActionNode* that) {
   RegExpNode* target = that->on_success();
   EnsureAnalyzed(target);
   // If the next node is interested in what it follows then this node
   // has to be interested too so it can pass the information on.
   that->info()->AddFromFollowing(target->info());
 }
 
 
-void Analysis::VisitChoice(ChoiceNode* that) {
+void AssertionPropagation::VisitChoice(ChoiceNode* that) {
   NodeInfo* info = that->info();
   for (int i = 0; i < that->alternatives()->length(); i++) {
     RegExpNode* node = that->alternatives()->at(i).node();
     EnsureAnalyzed(node);
     // Anything the following nodes need to know has to be known by
     // this node also, so it can pass it on.
     info->AddFromFollowing(node->info());
   }
 }
 
 
-void Analysis::VisitBackReference(BackReferenceNode* that) {
+void AssertionPropagation::VisitBackReference(BackReferenceNode* that) {
   EnsureAnalyzed(that->on_success());
 }
 
 
 // -------------------------------------------------------------------
 // Assumption expansion
 
 
 RegExpNode* RegExpNode::EnsureExpanded(NodeInfo* info) {
   siblings_.Ensure(this);
@@ skipping 294 matching lines @@
   }
 }
 
 
 void DispatchTableConstructor::VisitAction(ActionNode* that) {
   RegExpNode* target = that->on_success();
   target->Accept(this);
 }
 
 
-Handle<FixedArray> RegExpEngine::Compile(RegExpParseResult* input,
-                                         RegExpNode** node_return,
+#ifdef DEBUG
+
+
+class VisitNodeScope {
+ public:
+  explicit VisitNodeScope(RegExpNode* node) : node_(node) {
+    ASSERT(!node->info()->visited);
+    node->info()->visited = true;
+  }
+  ~VisitNodeScope() {
+    node_->info()->visited = false;
+  }
+ private:
+  RegExpNode* node_;
+};
+
+
+class NodeValidator : public NodeVisitor {
+ public:
+  virtual void ValidateInfo(NodeInfo* info) = 0;
+#define DECLARE_VISIT(Type)                                          \
+  virtual void Visit##Type(Type##Node* that);
+FOR_EACH_NODE_TYPE(DECLARE_VISIT)
+#undef DECLARE_VISIT
+};
+
+
+class PostAnalysisNodeValidator : public NodeValidator {
+ public:
+  virtual void ValidateInfo(NodeInfo* info);
+};
+
+
+class PostExpansionNodeValidator : public NodeValidator {
+ public:
+  virtual void ValidateInfo(NodeInfo* info);
+};
+
+
+void PostAnalysisNodeValidator::ValidateInfo(NodeInfo* info) {
+  ASSERT(info->been_analyzed);
+}
+
+
+void PostExpansionNodeValidator::ValidateInfo(NodeInfo* info) {
+  ASSERT_EQ(info->determine_newline, info->does_determine_newline);
+  ASSERT_EQ(info->determine_start, info->does_determine_start);
+  ASSERT_EQ(info->determine_word, info->does_determine_word);
+  ASSERT_EQ(info->follows_word_interest,
+            (info->follows_word != NodeInfo::UNKNOWN));
+  if (false) {
+    // These are still unimplemented.
+    ASSERT_EQ(info->follows_start_interest,
+              (info->follows_start != NodeInfo::UNKNOWN));
+    ASSERT_EQ(info->follows_newline_interest,
+              (info->follows_newline != NodeInfo::UNKNOWN));
+  }
+}
+
+
+void NodeValidator::VisitAction(ActionNode* that) {
+  if (that->info()->visited) return;
+  VisitNodeScope scope(that);
+  ValidateInfo(that->info());
+  that->on_success()->Accept(this);
+}
+
+
+void NodeValidator::VisitBackReference(BackReferenceNode* that) {
+  if (that->info()->visited) return;
+  VisitNodeScope scope(that);
+  ValidateInfo(that->info());
+  that->on_success()->Accept(this);
+}
+
+
+void NodeValidator::VisitChoice(ChoiceNode* that) {
+  if (that->info()->visited) return;
+  VisitNodeScope scope(that);
+  ValidateInfo(that->info());
+  ZoneList<GuardedAlternative>* alts = that->alternatives();
+  for (int i = 0; i < alts->length(); i++)
+    alts->at(i).node()->Accept(this);
+}
+
+
+void NodeValidator::VisitEnd(EndNode* that) {
+  if (that->info()->visited) return;
+  VisitNodeScope scope(that);
+  ValidateInfo(that->info());
+}
+
+
+void NodeValidator::VisitText(TextNode* that) {
+  if (that->info()->visited) return;
+  VisitNodeScope scope(that);
+  ValidateInfo(that->info());
+  that->on_success()->Accept(this);
+}
+
+
+#endif
+
+
+Handle<FixedArray> RegExpEngine::Compile(RegExpCompileData* data,
                                          bool ignore_case,
                                          bool is_multiline,
                                          Handle<String> pattern,
                                          bool is_ascii) {
-  RegExpCompiler compiler(input->capture_count, ignore_case, is_ascii);
+  RegExpCompiler compiler(data->capture_count, ignore_case, is_ascii);
   // Wrap the body of the regexp in capture #0.
-  RegExpNode* captured_body = RegExpCapture::ToNode(input->tree,
+  RegExpNode* captured_body = RegExpCapture::ToNode(data->tree,
                                                     0,
                                                     &compiler,
                                                     compiler.accept());
   // 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);
-  if (node_return != NULL) *node_return = node;
-  Analysis analysis(ignore_case);
+  AssertionPropagation analysis(ignore_case);
   analysis.EnsureAnalyzed(node);
 
   NodeInfo info = *node->info();
+  data->has_lookbehind = info.HasLookbehind();
+  if (data->has_lookbehind) {
+    // If this node needs information about the preceding text we let
+    // it start with a character class that consumes a single character
+    // and proceeds to wherever is appropriate.  This means that if
+    // has_lookbehind is set the code generator must start one character
+    // before the start position.
+    node = new TextNode(new RegExpCharacterClass('*'), node);
+    analysis.EnsureAnalyzed(node);
+  }
+
+#ifdef DEBUG
+  PostAnalysisNodeValidator post_analysis_validator;
+  node->Accept(&post_analysis_validator);
+#endif
+
   node = node->EnsureExpanded(&info);
 
+#ifdef DEBUG
+  PostExpansionNodeValidator post_expansion_validator;
+  node->Accept(&post_expansion_validator);
+#endif
+
+  data->node = node;
+
   if (is_multiline && !FLAG_attempt_multiline_irregexp) {
     return Handle<FixedArray>::null();
   }
 
+  if (data->has_lookbehind) {
+    return Handle<FixedArray>::null();
+  }
+
   if (FLAG_irregexp_native) {
 #ifdef ARM
     // Unimplemented, fall-through to bytecode implementation.
 #else  // IA32
     RegExpMacroAssemblerIA32::Mode mode;
     if (is_ascii) {
       mode = RegExpMacroAssemblerIA32::ASCII;
     } else {
       mode = RegExpMacroAssemblerIA32::UC16;
     }
     RegExpMacroAssemblerIA32 macro_assembler(mode,
-                                             (input->capture_count + 1) * 2);
+                                             (data->capture_count + 1) * 2);
     return compiler.Assemble(&macro_assembler,
                              node,
-                             input->capture_count,
+                             data->capture_count,
                              pattern);
 #endif
   }
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
-                           input->capture_count,
+                           data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal