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 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();
@@ skipping 425 matching lines @@
   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 1863 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:
+  explicit NodeValidator(bool has_been_expanded)
+      : has_been_expanded_(has_been_expanded) { }
+  void ValidateInfo(NodeInfo* info);
+#define DECLARE_VISIT(Type)                                          \
+  virtual void Visit##Type(Type##Node* that);
+FOR_EACH_NODE_TYPE(DECLARE_VISIT)
+#undef DECLARE_VISIT
+ private:
+  bool has_been_expanded_;

[Lasse Reichstein, 2008/12/11 08:34:23]

Isn't this really two different visitors, rolled into one with a boolean tag?
How about making ValidateInfo pure virtual, and have two different subclasses
that implement ValidateInfo differently (as each branch of the conditional in
the current NodeValidator::ValidateInfo).

[Christian Plesner Hansen, 2008/12/11 09:14:12]

Good point.

+};
+
+
+void NodeValidator::ValidateInfo(NodeInfo* info) {
+  if (has_been_expanded_) {
+    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));
+    }
+  } else {
+    ASSERT(info->been_analyzed);
+  }
+}
+
+
+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);

[Lasse Reichstein, 2008/12/11 08:34:23]

What happens if the look-behind is at the start of the string (there is no
character before the start position)? 
The current implementation preloads the previous character, or "\n" if at the
start of the string, so the code-generation can start out with a
current-character-test without reading. Will the code-generation be able to see
that this text node is the one before the real start?

[Christian Plesner Hansen, 2008/12/11 09:14:12]

Yes, it can use has_lookbehind to determine that.

+    analysis.EnsureAnalyzed(node);
+  }
+
+#ifdef DEBUG
+  NodeValidator pre_expansion_validator(false);
+  node->Accept(&pre_expansion_validator);
+#endif
+
   node = node->EnsureExpanded(&info);
 
+#ifdef DEBUG
+  NodeValidator post_expansion_validator(true);
+  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