* Have an ASCII and a UC16 interpreter for Irregexp bytecodes -...

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 944 matching lines @@
       rc = false;
       break;
 #endif
     }
     case RegExpMacroAssembler::kBytecodeImplementation: {
       for (int i = (num_captures + 1) * 2 - 1; i >= 0; i--) {
         offsets_vector[i] = -1;
       }
       Handle<ByteArray> byte_codes = IrregexpByteCode(irregexp);
 
-      Handle<String> two_byte_subject = CachedStringToTwoByte(subject);
+      if (!subject->IsFlat(StringShape(*subject))) {
+        FlattenString(subject);

[Lasse Reichstein, 2008/12/09 07:43:07]

The string is also flattened in the IA32 branch (line 889). You could move this
outside the switch.

+      }
 
       rc = IrregexpInterpreter::Match(byte_codes,
-                                      two_byte_subject,
+                                      subject,
                                       offsets_vector,
                                       previous_index);
       break;
     }
     case RegExpMacroAssembler::kARMImplementation:
     default:
       UNREACHABLE();
       rc = false;
       break;
   }
@@ skipping 205 matching lines @@
     table_ = new DispatchTable();
     DispatchTableConstructor cons(table_, ignore_case);
     cons.BuildTable(this);
   }
   return table_;
 }
 
 
 class RegExpCompiler {
  public:
-  RegExpCompiler(int capture_count, bool ignore_case);
+  RegExpCompiler(int capture_count, bool ignore_case, bool is_ascii);
 
   int AllocateRegister() { return next_register_++; }
 
   Handle<FixedArray> Assemble(RegExpMacroAssembler* assembler,
                               RegExpNode* start,
                               int capture_count,
                               Handle<String> pattern);
 
   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_; }
 
   static const int kMaxRecursion = 100;
   inline int recursion_depth() { return recursion_depth_; }
   inline void IncrementRecursionDepth() { recursion_depth_++; }
   inline void DecrementRecursionDepth() { recursion_depth_--; }
 
   inline bool ignore_case() { return ignore_case_; }
+  inline bool ascii() { return ascii_; }
 
  private:
   EndNode* accept_;
   int next_register_;
   List<RegExpNode*>* work_list_;
   int recursion_depth_;
   RegExpMacroAssembler* macro_assembler_;
   bool ignore_case_;
+  bool ascii_;
 };
 
 
 class RecursionCheck {
  public:
   explicit RecursionCheck(RegExpCompiler* compiler) : compiler_(compiler) {
     compiler->IncrementRecursionDepth();
   }
   ~RecursionCheck() { compiler_->DecrementRecursionDepth(); }
  private:
   RegExpCompiler* compiler_;
 };
 
 
 // Attempts to compile the regexp using an Irregexp code generator.  Returns
 // a fixed array or a null handle depending on whether it succeeded.
-RegExpCompiler::RegExpCompiler(int capture_count, bool ignore_case)
+RegExpCompiler::RegExpCompiler(int capture_count, bool ignore_case, bool ascii)
     : next_register_(2 * (capture_count + 1)),
       work_list_(NULL),
       recursion_depth_(0),
-      ignore_case_(ignore_case) {
+      ignore_case_(ignore_case),
+      ascii_(ascii) {
   accept_ = new EndNode(EndNode::ACCEPT);
 }
 
 
 Handle<FixedArray> RegExpCompiler::Assemble(
     RegExpMacroAssembler* macro_assembler,
     RegExpNode* start,
     int capture_count,
     Handle<String> pattern) {
 #ifdef DEBUG
@@ skipping 418 matching lines @@
       macro_assembler->LoadCurrentCharacterUnchecked(cp_offset + i);
     }
     Label ok;
     ASSERT(unibrow::Ecma262UnCanonicalize::kMaxWidth == 4);
     switch (length) {
       case 2: {
         if (ShortCutEmitCharacterPair(macro_assembler,
                                       chars[0],
                                       chars[1],
                                       on_failure)) {
-          ok.Unuse();
         } else {
           macro_assembler->CheckCharacter(chars[0], &ok);
           macro_assembler->CheckNotCharacter(chars[1], on_failure);
           macro_assembler->Bind(&ok);
         }
         break;
       }
       case 4:
         macro_assembler->CheckCharacter(chars[3], &ok);
         // Fall through!
       case 3:
         macro_assembler->CheckCharacter(chars[0], &ok);
         macro_assembler->CheckCharacter(chars[1], &ok);
         macro_assembler->CheckNotCharacter(chars[2], on_failure);
         macro_assembler->Bind(&ok);
         break;
       default:
         UNREACHABLE();
         break;
     }
   }
 }
 
 
 static void EmitCharClass(RegExpMacroAssembler* macro_assembler,
                           RegExpCharacterClass* cc,
                           int cp_offset,
                           Label* on_failure,
-                          bool check_offset) {
+                          bool check_offset,
+                          bool ascii) {
   ZoneList<CharacterRange>* ranges = cc->ranges();
+  const int max_char = ascii ? 0x7f : 0xffff;

[Lasse Reichstein, 2008/12/09 07:43:07]

Use String::kMaxAsciiCharCode instead of 0x7f?

 
   Label success;
 
   Label* char_is_in_class =
       cc->is_negated() ? on_failure : &success;
 
   int range_count = ranges->length();
 
-  if (range_count == 0) {
+  int last_valid_range = range_count - 1;
+  while (last_valid_range >= 0) {
+    CharacterRange& range = ranges->at(last_valid_range);
+    if (range.from() <= max_char) {
+      break;
+    }
+    last_valid_range--;
+  }
+
+  if (last_valid_range < 0) {
     if (!cc->is_negated()) {
+      // TODO(plesner): We can remove this when the node level does our
+      // ASCII optimizations for us.
       macro_assembler->GoTo(on_failure);
     }
     return;
   }
 
-  if (range_count == 1 &&
+  if (last_valid_range == 0 &&
       !cc->is_negated() &&
-      ranges->at(0).IsEverything(0xffff)) {
+      ranges->at(0).IsEverything(max_char)) {
     // This is a common case hit by non-anchored expressions.
     // TODO(erikcorry): We should have a macro assembler instruction that just
     // checks for end of string without loading the character.
     if (check_offset) {
       macro_assembler->LoadCurrentCharacter(cp_offset, on_failure);
     }
     return;
   }
 
   if (check_offset) {
     macro_assembler->LoadCurrentCharacter(cp_offset, on_failure);
   } else {
     // Here we don't need to check against the end of the input string
     // since this character lies before a character that matched.
     macro_assembler->LoadCurrentCharacterUnchecked(cp_offset);
   }
 
-  for (int i = 0; i < range_count - 1; i++) {
+  for (int i = 0; i <= last_valid_range; i++) {
     CharacterRange& range = ranges->at(i);
     Label next_range;
     uc16 from = range.from();
     uc16 to = range.to();
+    if (from > max_char) {
+      continue;
+    }
+    if (to > max_char) to = max_char;
     if (to == from) {
       macro_assembler->CheckCharacter(to, char_is_in_class);
     } else {
       if (from != 0) {
         macro_assembler->CheckCharacterLT(from, &next_range);

[Lasse Reichstein, 2008/12/09 07:43:07]

How about a CheckCharacterRange(from, to, char_is_in_class)?
That would allow the assembler to do the unsigned-range-check-hack? "if (x -
from < to - from) ..."

       }
-      if (to != 0xffff) {
+      if (to != max_char) {
         macro_assembler->CheckCharacterLT(to + 1, char_is_in_class);
       } else {
         macro_assembler->GoTo(char_is_in_class);
       }
     }
     macro_assembler->Bind(&next_range);
   }
 
-  CharacterRange& range = ranges->at(range_count - 1);
+  CharacterRange& range = ranges->at(last_valid_range);
   uc16 from = range.from();
   uc16 to = range.to();
 
+  if (to > max_char) to = max_char;
+  ASSERT(to >= from);
+
   if (to == from) {
     if (cc->is_negated()) {
       macro_assembler->CheckCharacter(to, on_failure);
     } else {
       macro_assembler->CheckNotCharacter(to, on_failure);
     }
   } else {
     if (from != 0) {
       if (cc->is_negated()) {
         macro_assembler->CheckCharacterLT(from, &success);
@@ skipping 83 matching lines @@
   if (limit_result == FAIL) return false;
   if (limit_result == DONE) return true;
   ASSERT(limit_result == CONTINUE);
 
   int element_count = elms_->length();
   ASSERT(element_count != 0);
   if (info()->at_end) {
     macro_assembler->GoTo(backtrack);
     return true;
   }
-  // First, handle straight character matches.
+  // First check for non-ASCII text.
+  // TODO(plesner): We should do this at node level.
+  if (compiler->ascii()) {
+    for (int i = element_count - 1; i >= 0; i--) {
+      TextElement elm = elms_->at(i);
+      if (elm.type == TextElement::ATOM) {
+        Vector<const uc16> quarks = elm.data.u_atom->data();
+        for (int j = quarks.length() - 1; j >= 0; j--) {
+          if (quarks[j] > 0x7f) {

[Lasse Reichstein, 2008/12/09 07:43:07]

Use String::kMaxAsciiCharCode

+            macro_assembler->GoTo(backtrack);
+            return true;
+          }
+        }
+      } else {
+        ASSERT_EQ(elm.type, TextElement::CHAR_CLASS);
+      }
+    }
+  }
+  // Second, handle straight character matches.
   int checked_up_to = -1;
   for (int i = element_count - 1; i >= 0; i--) {
     TextElement elm = elms_->at(i);
     ASSERT(elm.cp_offset >= 0);
     int cp_offset = variant->cp_offset() + elm.cp_offset;
     if (elm.type == TextElement::ATOM) {
       Vector<const uc16> quarks = elm.data.u_atom->data();
       int last_cp_offset = cp_offset + quarks.length();
       if (compiler->ignore_case()) {
         EmitAtomNonLetters(macro_assembler,
                            elm,
                            quarks,
                            backtrack,
                            cp_offset,
                            checked_up_to < last_cp_offset);
       } else {
         macro_assembler->CheckCharacters(quarks,
                                          cp_offset,
                                          backtrack,
                                          checked_up_to < last_cp_offset);
       }
       if (last_cp_offset > checked_up_to) checked_up_to = last_cp_offset - 1;
     } else {
       ASSERT_EQ(elm.type, TextElement::CHAR_CLASS);
     }
   }
-  // Second, handle case independent letter matches if any.
+  // Third, handle case independent letter matches if any.
   if (compiler->ignore_case()) {
     for (int i = element_count - 1; i >= 0; i--) {
       TextElement elm = elms_->at(i);
       int cp_offset = variant->cp_offset() + elm.cp_offset;
       if (elm.type == TextElement::ATOM) {
         Vector<const uc16> quarks = elm.data.u_atom->data();
         int last_cp_offset = cp_offset + quarks.length();
         EmitAtomLetters(macro_assembler,
                         elm,
                         quarks,
                         backtrack,
                         cp_offset,
                         checked_up_to < last_cp_offset);
         if (last_cp_offset > checked_up_to) checked_up_to = last_cp_offset - 1;
       }
     }
   }
   // If the fast character matches passed then do the character classes.
   for (int i = element_count - 1; i >= 0; i--) {
     TextElement elm = elms_->at(i);
     int cp_offset = variant->cp_offset() + elm.cp_offset;
     if (elm.type == TextElement::CHAR_CLASS) {
       RegExpCharacterClass* cc = elm.data.u_char_class;
       EmitCharClass(macro_assembler,
                     cc,
                     cp_offset,
                     backtrack,
-                    checked_up_to < cp_offset);
+                    checked_up_to < cp_offset,
+                    compiler->ascii());
       if (cp_offset > checked_up_to) checked_up_to = cp_offset;
     }
   }
 
   GenerationVariant new_variant(*variant);
   new_variant.set_cp_offset(checked_up_to + 1);
   RecursionCheck rc(compiler);
   return on_success()->Emit(compiler, &new_variant);
 }
 
@@ skipping 1660 matching lines @@
   target->Accept(this);
 }
 
 
 Handle<FixedArray> RegExpEngine::Compile(RegExpParseResult* input,
                                          RegExpNode** node_return,
                                          bool ignore_case,
                                          bool is_multiline,
                                          Handle<String> pattern,
                                          bool is_ascii) {
-  RegExpCompiler compiler(input->capture_count, ignore_case);
+  RegExpCompiler compiler(input->capture_count, ignore_case, is_ascii);
   // Wrap the body of the regexp in capture #0.
   RegExpNode* captured_body = RegExpCapture::ToNode(input->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.
@@ skipping 35 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            input->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal