Irregexp:...

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 1721 matching lines @@
                                     trace->backtrack());
       break;
   }
 }
 
 
 static unibrow::Mapping<unibrow::Ecma262UnCanonicalize> uncanonicalize;
 static unibrow::Mapping<unibrow::CanonicalizationRange> canonrange;
 
 
+// Returns the number of characters in the equivalence class, omitting those
+// that cannot occur in the source string because it is ASCII.
+static int GetCaseIndependentLetters(uc16 character,
+                                     bool ascii_subject,
+                                     unibrow::uchar* letters) {
+  int length = uncanonicalize.get(character, '\0', letters);
+  // Unibrow returns 0 or 1 for characters where case independependence is
+  // trivial.
+  if (length == 0) {
+    letters[0] = character;
+    length = 1;
+  }
+  if (!ascii_subject || character <= String::kMaxAsciiCharCode) {
+    return length;
+  }
+  // The standard requires that non-ASCII characters cannot have ASCII
+  // character codes in their equivalence class.
+  return 0;
+}
+
+
 // Only emits non-letters (things that don't have case).  Only used for case
 // independent matches.
 static inline bool EmitAtomNonLetter(
     RegExpMacroAssembler* macro_assembler,
     uc16 c,
+    bool ascii,
     Label* on_failure,
     int cp_offset,
     bool check,
     bool preloaded) {
   unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
-  int length = uncanonicalize.get(c, '\0', chars);
+  int length = GetCaseIndependentLetters(c, ascii, chars);
+  if (length < 1) {
+    // This can't match.  Must be an ASCII subject and a non-ASCII character.
+    // We do not need to do anything since the ASCII pass already handled this.
+    return false;  // Bounds not checked.
+  }
   bool checked = false;
-  if (length <= 1) {
+  // We handle the length > 1 case in a later pass.
+  if (length == 1) {
+    if (ascii && c > String::kMaxAsciiCharCodeU) {
+      // Can't match - see above.
+      return false;  // Bounds not checked.
+    }
     if (!preloaded) {
       macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check);
       checked = check;
     }
     macro_assembler->CheckNotCharacter(c, on_failure);
   }
   return checked;
 }
 
 
@@ skipping 33 matching lines @@
     return true;
   }
   return false;
 }
 
 
 // Only emits letters (things that have case).  Only used for case independent
 // matches.
 static inline bool EmitAtomLetter(
     RegExpMacroAssembler* macro_assembler,
+    uc16 c,
     bool ascii,
-    uc16 c,
     Label* on_failure,
     int cp_offset,
     bool check,
     bool preloaded) {
   unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
-  int length = uncanonicalize.get(c, '\0', chars);
+  int length = GetCaseIndependentLetters(c, ascii, chars);
   if (length <= 1) return false;
   // We may not need to check against the end of the input string
   // if this character lies before a character that matched.
   if (!preloaded) {
     macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check);
   }
   Label ok;
   ASSERT(unibrow::Ecma262UnCanonicalize::kMaxWidth == 4);
   switch (length) {
     case 2: {
@@ skipping 21 matching lines @@
     default:
       UNREACHABLE();
       break;
   }
   return true;
 }
 
 
 static void EmitCharClass(RegExpMacroAssembler* macro_assembler,
                           RegExpCharacterClass* cc,
+                          bool ascii,
+                          Label* on_failure,
                           int cp_offset,
-                          Label* on_failure,
                           bool check_offset,
-                          bool ascii,
                           bool preloaded) {
   if (cc->is_standard() &&
       macro_assembler->CheckSpecialCharacterClass(cc->standard_type(),
                                                   cp_offset,
                                                   check_offset,
                                                   on_failure)) {
     return;
   }
 
   ZoneList<CharacterRange>* ranges = cc->ranges();
@@ skipping 360 matching lines @@
       for (int i = 0; i < characters && i < quarks.length(); i++) {
         QuickCheckDetails::Position* pos =
             details->positions(characters_filled_in);
         uc16 c = quarks[i];
         if (c > char_mask) {
           // If we expect a non-ASCII character from an ASCII string,
           // there is no way we can match. Not even case independent
           // matching can turn an ASCII character into non-ASCII or
           // vice versa.
           details->set_cannot_match();
+          pos->determines_perfectly = false;

[Lasse Reichstein, 2009/02/18 15:20:44]

Should this be set to false? If the remaining cases of a choice node are
actually determined perfectly, we should match them.
I.e., treat a cannot-match result as if it wasn't there at all.

[Erik Corry, 2009/02/18 16:04:24]

Determines perfectly indicates that this particular character position has been
checked completely by the quick check.  The implication is that if we get past
the quick check then we don't need to look at this character position again.  So
'false' would be wrong here.

           return;
         }
         if (compiler->ignore_case()) {
           unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
-          int length = uncanonicalize.get(c, '\0', chars);
-          if (length < 2) {
+          int length = GetCaseIndependentLetters(c, compiler->ascii(), chars);
+          ASSERT(length != 0);  // Can only happen if c > char_mask (see above).
+          if (length == 1) {
             // This letter has no case equivalents, so it's nice and simple
             // and the mask-compare will determine definitely whether we have
             // a match at this character position.
             pos->mask = char_mask;
             pos->value = c;
             pos->determines_perfectly = true;
           } else {
             uint32_t common_bits = char_mask;
             uint32_t bits = chars[0];
             for (int j = 1; j < length; j++) {
@@ skipping 24 matching lines @@
         ASSERT(characters_filled_in <= details->characters());
         if (characters_filled_in == details->characters()) {
           return;
         }
       }
     } else {
       QuickCheckDetails::Position* pos =
           details->positions(characters_filled_in);
       RegExpCharacterClass* tree = elm.data.u_char_class;
       ZoneList<CharacterRange>* ranges = tree->ranges();
-      CharacterRange range = ranges->at(0);
       if (tree->is_negated()) {
         // A quick check uses multi-character mask and compare.  There is no
         // useful way to incorporate a negative char class into this scheme
         // so we just conservatively create a mask and value that will always
         // succeed.

[Lasse Reichstein, 2009/02/18 15:20:44]

This comment should be changed to just "not yet handled".
It would be fairly easy to normalize the character class representation to be
non-negated and treat it like a positive class.

[Erik Corry, 2009/02/18 16:04:24]

I don't think that char classes like [^\u0000-ac-\uffff] are common enough to
warrant spending time on, ever.

         pos->mask = 0;
         pos->value = 0;
       } else {
-        uint32_t differing_bits = (range.from() ^ range.to());
+        int first_range = 0;
+        while (ranges->at(first_range).from() > char_mask) {
+          first_range++;
+          if (first_range == ranges->length()) {
+            details->set_cannot_match();
+            pos->determines_perfectly = false;
+            return;
+          }
+        }
+        CharacterRange range = ranges->at(first_range);
+        uc16 from = range.from();
+        uc16 to = range.to();
+        if (to > char_mask) {
+          to = char_mask;
+        }
+        uint32_t differing_bits = (from ^ to);
         // A mask and compare is only perfect if the differing bits form a
         // number like 00011111 with one single block of trailing 1s.
         if ((differing_bits & (differing_bits + 1)) == 0) {
           pos->determines_perfectly = true;
         }
         uint32_t common_bits = ~SmearBitsRight(differing_bits);
-        uint32_t bits = (range.from() & common_bits);
-        for (int i = 1; i < ranges->length(); i++) {
+        uint32_t bits = (from & common_bits);
+        for (int i = first_range + 1; i < ranges->length(); i++) {
+          CharacterRange range = ranges->at(i);
+          uc16 from = range.from();
+          uc16 to = range.to();
+          if (from > char_mask) continue;
+          if (to > char_mask) to = char_mask;
           // Here we are combining more ranges into the mask and compare
           // value.  With each new range the mask becomes more sparse and
           // so the chances of a false positive rise.  A character class
           // with multiple ranges is assumed never to be equivalent to a
           // mask and compare operation.
           pos->determines_perfectly = false;
-          CharacterRange range = ranges->at(i);
-          uint32_t new_common_bits = (range.from() ^ range.to());
+          uint32_t new_common_bits = (from ^ to);
           new_common_bits = ~SmearBitsRight(new_common_bits);
           common_bits &= new_common_bits;
           bits &= new_common_bits;
-          uint32_t differing_bits = (range.from() & common_bits) ^ bits;
+          uint32_t differing_bits = (from & common_bits) ^ bits;
           common_bits ^= differing_bits;
           bits &= common_bits;
         }
         pos->mask = common_bits;
         pos->value = bits;
       }
       characters_filled_in++;
       ASSERT(characters_filled_in <= details->characters());
       if (characters_filled_in == details->characters()) {
         return;
@@ skipping 281 matching lines @@
       return;
     case AT_NON_BOUNDARY:
     case AT_BOUNDARY:
       EmitBoundaryCheck(type_, compiler, on_success(), trace);
       return;
   }
   on_success()->Emit(compiler, trace);
 }
 
 
+static bool DeterminedAlready(QuickCheckDetails* quick_check, int offset) {
+  if (quick_check == NULL) return false;
+  if (offset >= quick_check->characters()) return false;
+  return quick_check->positions(offset)->determines_perfectly;

[Lasse Reichstein, 2009/02/18 15:20:44]

Just checking: If we find that a position determines the branch perfectly, will
the position always be tested? Or is it possible that, e.g., both the first and
second character perfectly determines the branch, and only the first is actually
checked?

[Erik Corry, 2009/02/18 16:04:24]

See above.

+}
+
+
+static void UpdateBoundsCheck(int index, int* checked_up_to) {
+  if (index > *checked_up_to) {
+    *checked_up_to = index;
+  }
+}
+
+
 // We call this repeatedly to generate code for each pass over the text node.
 // The passes are in increasing order of difficulty because we hope one
 // of the first passes will fail in which case we are saved the work of the
 // later passes.  for example for the case independent regexp /%[asdfghjkl]a/
 // we will check the '%' in the first pass, the case independent 'a' in the
 // second pass and the character class in the last pass.
 //
 // The passes are done from right to left, so for example to test for /bar/
 // we will first test for an 'r' with offset 2, then an 'a' with offset 1
 // and then a 'b' with offset 0.  This means we can avoid the end-of-input
@@ skipping 14 matching lines @@
 // order to get to the code we are now generating.  The quick check can involve
 // loading characters, which means we do not need to recheck the bounds
 // up to the limit the quick check already checked.  In addition the quick
 // check can have involved a mask and compare operation which may simplify
 // or obviate the need for further checks at some character positions.
 void TextNode::TextEmitPass(RegExpCompiler* compiler,
                             TextEmitPassType pass,
                             bool preloaded,
                             Trace* trace,
                             bool first_element_checked,
                             int* checked_up_to) {

[Lasse Reichstein, 2009/02/18 15:20:44]

This function is one big glob of special cases.
If the different passes has something in common, please refactor it to, e.g., a
template function or pass objects with virtual methods or something else that
avoids putting all the cases in one monolithic function.

[Erik Corry, 2009/02/18 16:04:24]

I've refactored a little more.  It is now only 68 lines with 30 lines of
comments to explain what it is doing.  I feel that making it much smaller will
either cause code duplication or unnecessary abstraction boilerplace elsewhere.

   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   bool ascii = compiler->ascii();
   Label* backtrack = trace->backtrack();
   QuickCheckDetails* quick_check = trace->quick_check_performed();
   int element_count = elms_->length();
   for (int i = preloaded ? 0 : element_count - 1; i >= 0; i--) {
     TextElement elm = elms_->at(i);
     int cp_offset = trace->cp_offset() + elm.cp_offset;
     if (elm.type == TextElement::ATOM) {
-      if (pass == NON_ASCII_MATCH ||
-          pass == CHARACTER_MATCH ||
-          pass == CASE_CHARACTER_MATCH) {
+      if (pass != CHARACTER_CLASS_MATCH) {
         Vector<const uc16> quarks = elm.data.u_atom->data();
         for (int j = preloaded ? 0 : quarks.length() - 1; j >= 0; j--) {
-          bool bound_checked = true;  // Most ops will check their bounds.
+          bool bound_checked = false;
           if (first_element_checked && i == 0 && j == 0) continue;
-          if (pass == NON_ASCII_MATCH) {
-            ASSERT(ascii);
-            if (quarks[j] > String::kMaxAsciiCharCode) {
-              assembler->GoTo(backtrack);
-              return;
-            }
-          } else {
-            if (quick_check != NULL &&
-                elm.cp_offset + j < quick_check->characters() &&
-                quick_check->positions(elm.cp_offset + j)->
-                    determines_perfectly) {
-              continue;
-            }
-            if (pass == CHARACTER_MATCH) {
-              if (compiler->ignore_case()) {
-                bound_checked = EmitAtomNonLetter(
-                    assembler,
-                    quarks[j],
+          if (DeterminedAlready(quick_check, elm.cp_offset + j)) continue;
+          switch (pass) {
+            case NON_ASCII_MATCH:
+              ASSERT(ascii);
+              if (quarks[j] > String::kMaxAsciiCharCode) {
+                assembler->GoTo(backtrack);
+                return;
+              }
+              break;
+            case NON_LETTER_CHARACTER_MATCH:
+              bound_checked = EmitAtomNonLetter(assembler,
+                                                quarks[j],
+                                                ascii,
+                                                backtrack,
+                                                cp_offset + j,
+                                                *checked_up_to < cp_offset + j,
+                                                preloaded);
+              break;
+            case SIMPLE_CHARACTER_MATCH:
+              if (!preloaded) {
+                assembler->LoadCurrentCharacter(
+                    cp_offset + j,
                     backtrack,
-                    cp_offset + j,
-                    *checked_up_to < cp_offset + j,
-                    preloaded);
-              } else {
-                if (!preloaded) {
-                  assembler->LoadCurrentCharacter(
-                      cp_offset + j,
-                      backtrack,
-                      *checked_up_to < cp_offset + j);
-                }
-                assembler->CheckNotCharacter(quarks[j], backtrack);
+                    *checked_up_to < cp_offset + j);
+                bound_checked = true;
               }
-            } else {
-              ASSERT_EQ(pass, CASE_CHARACTER_MATCH);
-              ASSERT(compiler->ignore_case());
+              assembler->CheckNotCharacter(quarks[j], backtrack);
+              break;
+            case CASE_CHARACTER_MATCH:
               bound_checked = EmitAtomLetter(assembler,
-                                             compiler->ascii(),
                                              quarks[j],
+                                             ascii,
                                              backtrack,
                                              cp_offset + j,
                                              *checked_up_to < cp_offset + j,
                                              preloaded);
-            }
-            if (bound_checked) {
-              if (cp_offset + j > *checked_up_to) {
-                *checked_up_to = cp_offset + j;
-              }
-            }
+              break;
+            default:
+              break;
           }
+          if (bound_checked) UpdateBoundsCheck(cp_offset + j, checked_up_to);
         }
       }
     } else {
       ASSERT_EQ(elm.type, TextElement::CHAR_CLASS);
-      if (first_element_checked && i == 0) continue;
-      if (quick_check != NULL &&
-          elm.cp_offset < quick_check->characters() &&
-          quick_check->positions(elm.cp_offset)->determines_perfectly) {
-        continue;
-      }
       if (pass == CHARACTER_CLASS_MATCH) {
+        if (first_element_checked && i == 0) continue;
+        if (DeterminedAlready(quick_check, elm.cp_offset)) continue;
         RegExpCharacterClass* cc = elm.data.u_char_class;
         EmitCharClass(assembler,
                       cc,
+                      ascii,
+                      backtrack,
                       cp_offset,
-                      backtrack,
                       *checked_up_to < cp_offset,
-                      ascii,
                       preloaded);
-        if (cp_offset > *checked_up_to) {
-          *checked_up_to = cp_offset;
-        }
+        UpdateBoundsCheck(cp_offset, checked_up_to);
       }
     }
   }
 }
 
 
 int TextNode::Length() {
   TextElement elm = elms_->last();
   ASSERT(elm.cp_offset >= 0);
   if (elm.type == TextElement::ATOM) {
     return elm.cp_offset + elm.data.u_atom->data().length();
   } else {
     return elm.cp_offset + 1;
   }
 }
 
 
+bool TextNode::SkipPass(int int_pass, bool ignore_case) {
+  TextEmitPassType pass = static_cast<TextEmitPassType>(int_pass);
+  if (ignore_case) {
+    return pass == SIMPLE_CHARACTER_MATCH;
+  } else {
+    return pass == NON_LETTER_CHARACTER_MATCH || pass == CASE_CHARACTER_MATCH;
+  }
+}
+
+
 // This generates the code to match a text node.  A text node can contain
 // straight character sequences (possibly to be matched in a case-independent
 // way) and character classes.  For efficiency we do not do this in a single
 // pass from left to right.  Instead we pass over the text node several times,
 // emitting code for some character positions every time.  See the comment on
 // TextEmitPass for details.
 void TextNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == DONE) return;
   ASSERT(limit_result == CONTINUE);
 
   if (trace->cp_offset() + Length() > RegExpMacroAssembler::kMaxCPOffset) {
     compiler->SetRegExpTooBig();
     return;
   }
 
   if (compiler->ascii()) {
     int dummy = 0;
     TextEmitPass(compiler, NON_ASCII_MATCH, false, trace, false, &dummy);
   }
 
   bool first_elt_done = false;
   int bound_checked_to = trace->cp_offset() - 1;
   bound_checked_to += trace->bound_checked_up_to();
 
   // If a character is preloaded into the current character register then
   // check that now.
   if (trace->characters_preloaded() == 1) {
-    TextEmitPass(compiler,
-                 CHARACTER_MATCH,
-                 true,
-                 trace,
-                 false,
-                 &bound_checked_to);
-    if (compiler->ignore_case()) {
-      TextEmitPass(compiler,
-                   CASE_CHARACTER_MATCH,
-                   true,
-                   trace,
-                   false,
-                   &bound_checked_to);
+    for (int pass = kFirstRealPass; pass <= kLastPass; pass++) {
+      if (!SkipPass(pass, compiler->ignore_case())) {
+        TextEmitPass(compiler,
+                     static_cast<TextEmitPassType>(pass),
+                     true,
+                     trace,
+                     false,
+                     &bound_checked_to);
+      }
     }
-    TextEmitPass(compiler,
-                 CHARACTER_CLASS_MATCH,
-                 true,
-                 trace,
-                 false,
-                 &bound_checked_to);
     first_elt_done = true;
   }
 
-  TextEmitPass(compiler,
-               CHARACTER_MATCH,
-               false,
-               trace,
-               first_elt_done,
-               &bound_checked_to);
-  if (compiler->ignore_case()) {
-    TextEmitPass(compiler,
-                 CASE_CHARACTER_MATCH,
-                 false,
-                 trace,
-                 first_elt_done,
-                 &bound_checked_to);
+  for (int pass = kFirstRealPass; pass <= kLastPass; pass++) {
+    if (!SkipPass(pass, compiler->ignore_case())) {
+      TextEmitPass(compiler,
+                   static_cast<TextEmitPassType>(pass),
+                   false,
+                   trace,
+                   first_elt_done,
+                   &bound_checked_to);
+    }
   }
-  TextEmitPass(compiler,
-               CHARACTER_CLASS_MATCH,
-               false,
-               trace,
-               first_elt_done,
-               &bound_checked_to);
 
   Trace successor_trace(*trace);
   successor_trace.set_at_start(false);
   successor_trace.AdvanceCurrentPositionInTrace(Length(), compiler);
   RecursionCheck rc(compiler);
   on_success()->Emit(compiler, &successor_trace);
 }
 
 
 void Trace::InvalidateCurrentCharacter() {
@@ skipping 2043 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal