More assertion propagation.

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 200 matching lines @@
   Handle<FixedArray> cached = CompilationCache::LookupRegExp(pattern, flags);
   bool in_cache = !cached.is_null();
   Handle<Object> result;
   if (in_cache) {
     re->set_data(*cached);
     result = re;
   } else {
     FlattenString(pattern);
     RegExpParseResult parse_result;
     FlatStringReader reader(pattern);
-    if (!ParseRegExp(&reader, &parse_result)) {
+    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>();
     }
     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);
       }
     } else {
       RegExpNode* node = NULL;
       Handle<FixedArray> irregexp_data =
           RegExpEngine::Compile(&parse_result,
                                 &node,
-                                flags.is_ignore_case());
+                                flags.is_ignore_case(),
+                                flags.is_multiline());
       if (irregexp_data.is_null()) {
         if (FLAG_disable_jscre) {
           UNIMPLEMENTED();
         }
         result = JscrePrepare(re, pattern, flags);
       } else {
         result = IrregexpPrepare(re, pattern, flags, irregexp_data);
       }
     }
     Object* data = re->data();
@@ skipping 718 matching lines @@
   array->set(RegExpImpl::kIrregexpCodeIndex, *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) {
+      info_.follows_start_interest ||
+      info_.at_end) {
     return false;
   }
   if (label_.is_bound()) {
     compiler->macro_assembler()->GoTo(&label_);
     return true;
   } else {
     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) {
+  if (info_.follows_word_interest ||
+      info_.follows_newline_interest ||
+      info_.follows_start_interest ||
+      info_.at_end) {
     return false;
   }
   if (!label()->is_bound()) {
     Bind(compiler->macro_assembler());
   }
   switch (action_) {
     case ACCEPT:
       compiler->macro_assembler()->Succeed();
       break;
     case BACKTRACK:
@@ skipping 604 matching lines @@
   StringStream* stream() { return stream_; }
   StringStream* stream_;
 };
 
 
 void DotPrinter::PrintAttributes(RegExpNode* that) {
   stream()->Add("  a%p [shape=Mrecord, style=dashed, color=lightgrey, "
                 "fontcolor=lightgrey, margin=0.1, fontsize=10, label=\"{",
                 that);
   NodeInfo* info = that->info();
-  stream()->Add("{NI|%i}|{SI|%i}|{WI|%i}",
+  stream()->Add("{NI|%i}|{WI|%i}|{SI|%i}",
                 info->follows_newline_interest,
-                info->follows_start_interest,
-                info->follows_word_interest);
-  stream()->Add("|{DN|%i}|{DS|%i}|{DW|%i}",
+                info->follows_word_interest,
+                info->follows_start_interest);
+  stream()->Add("|{DN|%i}|{DW|%i}|{DS|%i}|{AE|%i}",
                 info->determine_newline,
+                info->determine_word,
                 info->determine_start,
-                info->determine_word);
+                info->at_end);
+  if (info->follows_newline != NodeInfo::UNKNOWN)
+    stream()->Add("|{FN|%i}", info->follows_newline);
+  if (info->follows_word != NodeInfo::UNKNOWN)
+    stream()->Add("|{FW|%i}", info->follows_word);
+  if (info->follows_start != NodeInfo::UNKNOWN)
+    stream()->Add("|{FS|%i}", info->follows_start);
   Label* label = that->label();
   if (label->is_bound())
     stream()->Add("|{@|%x}", label->pos());
   stream()->Add("}\"];\n");
   stream()->Add("  a%p -> n%p [style=dashed, color=lightgrey, "
                 "arrowhead=none];\n", that, that);
 }
 
 
 void DotPrinter::VisitChoice(ChoiceNode* that) {
@@ skipping 267 matching lines @@
   switch (type()) {
     case START_OF_LINE:
       info.follows_newline_interest = true;
       break;
     case START_OF_INPUT:
       info.follows_start_interest = true;
       break;
     case BOUNDARY: case NON_BOUNDARY:
       info.follows_word_interest = true;
       break;
-    case END_OF_LINE: case END_OF_INPUT:
+    case END_OF_INPUT:
+      info.at_end = true;
+      break;
+    case END_OF_LINE:
       // This is wrong but has the effect of making the compiler abort.
-      info.follows_start_interest = true;
+      info.at_end = true;
   }
-  return on_success->PropagateInterest(&info);
+  return on_success->PropagateForward(&info);
 }
 
 
 RegExpNode* RegExpBackReference::ToNode(RegExpCompiler* compiler,
                                         RegExpNode* on_success,
                                         RegExpNode* on_failure) {
   return new BackReferenceNode(RegExpCapture::StartRegister(index()),
                                RegExpCapture::EndRegister(index()),
                                on_success,
                                on_failure);
@@ skipping 267 matching lines @@
 }
 
 
 // -------------------------------------------------------------------
 // Interest propagation
 
 
 RegExpNode* RegExpNode::GetSibling(NodeInfo* info) {
   for (int i = 0; i < siblings_.length(); i++) {
     RegExpNode* sibling = siblings_.Get(i);
-    if (sibling->info()->SameInterests(info))
+    if (sibling->info()->HasSameForwardInterests(info))
       return sibling;
   }
   return NULL;
 }
 
 
 template <class C>
 static RegExpNode* PropagateToEndpoint(C* node, NodeInfo* info) {
-  RegExpNode* sibling = node->GetSibling(info);
+  NodeInfo full_info(*node->info());
+  full_info.AddFromPreceding(info);
+  RegExpNode* sibling = node->GetSibling(&full_info);
   if (sibling != NULL) return sibling;
   node->EnsureSiblings();
   sibling = new C(*node);
-  sibling->info()->AdoptInterests(info);
+  sibling->info()->AddFromPreceding(&full_info);
   node->AddSibling(sibling);
   return sibling;
 }
 
 
-RegExpNode* ActionNode::PropagateInterest(NodeInfo* info) {
-  RegExpNode* sibling = GetSibling(info);
+RegExpNode* ActionNode::PropagateForward(NodeInfo* info) {
+  NodeInfo full_info(*this->info());
+  full_info.AddFromPreceding(info);
+  RegExpNode* sibling = GetSibling(&full_info);
   if (sibling != NULL) return sibling;
   EnsureSiblings();
   ActionNode* action = new ActionNode(*this);
-  action->info()->AdoptInterests(info);
+  action->info()->AddFromPreceding(&full_info);
   AddSibling(action);
-  action->set_on_success(action->on_success()->PropagateInterest(info));
+  action->set_on_success(action->on_success()->PropagateForward(info));
   return action;
 }
 
 
-RegExpNode* ChoiceNode::PropagateInterest(NodeInfo* info) {
-  RegExpNode* sibling = GetSibling(info);
+RegExpNode* ChoiceNode::PropagateForward(NodeInfo* info) {
+  NodeInfo full_info(*this->info());
+  full_info.AddFromPreceding(info);
+  RegExpNode* sibling = GetSibling(&full_info);
   if (sibling != NULL) return sibling;
   EnsureSiblings();
   ChoiceNode* choice = new ChoiceNode(*this);
-  choice->info()->AdoptInterests(info);
+  choice->info()->AddFromPreceding(&full_info);
   AddSibling(choice);
   ZoneList<GuardedAlternative>* old_alternatives = alternatives();
   int count = old_alternatives->length();
   choice->alternatives_ = new ZoneList<GuardedAlternative>(count);
   for (int i = 0; i < count; i++) {
     GuardedAlternative alternative = old_alternatives->at(i);
-    alternative.set_node(alternative.node()->PropagateInterest(info));
+    alternative.set_node(alternative.node()->PropagateForward(info));
     choice->alternatives()->Add(alternative);
   }
   return choice;
 }
 
 
-RegExpNode* EndNode::PropagateInterest(NodeInfo* info) {
+RegExpNode* EndNode::PropagateForward(NodeInfo* info) {
   return PropagateToEndpoint(this, info);
 }
 
 
-RegExpNode* BackReferenceNode::PropagateInterest(NodeInfo* info) {
+RegExpNode* BackReferenceNode::PropagateForward(NodeInfo* info) {
   return PropagateToEndpoint(this, info);
 }
 
 
-RegExpNode* TextNode::PropagateInterest(NodeInfo* info) {
+RegExpNode* TextNode::PropagateForward(NodeInfo* info) {
   return PropagateToEndpoint(this, info);
 }
 
 
 // -------------------------------------------------------------------
 // Splay tree
 
 
 OutSet* OutSet::Extend(unsigned value) {
   if (Get(value))
@@ skipping 158 matching lines @@
   // nothing to do
 }
 
 
 void Analysis::VisitText(TextNode* that) {
   if (ignore_case_) {
     that->MakeCaseIndependent();
   }
   EnsureAnalyzed(that->on_success());
   EnsureAnalyzed(that->on_failure());
+  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;
 }
 
 
 void Analysis::VisitAction(ActionNode* that) {
-  RegExpNode* next = that->on_success();
-  EnsureAnalyzed(next);
-  that->info()->determine_newline = next->info()->prev_determine_newline();
-  that->info()->determine_word = next->info()->prev_determine_word();
-  that->info()->determine_start = next->info()->prev_determine_start();
+  EnsureAnalyzed(that->on_success());
+  // 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(that->on_success()->info());
 }
 
 
 void Analysis::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);
-    info->determine_newline |= node->info()->prev_determine_newline();
-    info->determine_word |= node->info()->prev_determine_word();
-    info->determine_start |= node->info()->prev_determine_start();
+    // 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());
   }
   if (!that->table_calculated()) {
     DispatchTableConstructor cons(that->table());
     cons.BuildTable(that);
   }
   EnsureAnalyzed(that->on_failure());
 }
 
 
 void Analysis::VisitBackReference(BackReferenceNode* that) {
@@ skipping 112 matching lines @@
 }
 
 
 void DispatchTableConstructor::VisitAction(ActionNode* that) {
   that->on_success()->Accept(this);
 }
 
 
 Handle<FixedArray> RegExpEngine::Compile(RegExpParseResult* input,
                                          RegExpNode** node_return,
-                                         bool ignore_case) {
+                                         bool ignore_case,
+                                         bool is_multiline) {
   RegExpCompiler compiler(input->capture_count, ignore_case);
   // Wrap the body of the regexp in capture #0.
   RegExpNode* captured_body = RegExpCapture::ToNode(input->tree,
                                                     0,
                                                     &compiler,
                                                     compiler.accept(),
                                                     compiler.backtrack());
   // 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
@@ skipping 28 matching lines @@
   byte codes[1024];
   IrregexpAssembler assembler(Vector<byte>(codes, 1024));
   RegExpMacroAssemblerIrregexp macro_assembler(&assembler);
   return compiler.Assemble(&macro_assembler,
                            node,
                            input->capture_count);
 }
 
 
 }}  // namespace v8::internal