RegExp: Add support for table-based character class

src/jsregexp.cc

 // Copyright 2011 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 1516 matching lines @@
       macro_assembler->Bind(&ok);
       break;
     default:
       UNREACHABLE();
       break;
   }
   return true;
 }
 
 
+static void EmitBoundaryTest(RegExpMacroAssembler* masm,
+                             int border,
+                             Label* fall_through,
+                             Label* above,

[ulan, 2012/03/27 11:02:43]

'above_or_equal' would be more precise name.

[Erik Corry, 2012/03/28 09:40:26]

Done.

+                             Label* below) {
+  if (below != fall_through) {
+    masm->CheckCharacterLT(border, below);
+    if (above != fall_through) masm->GoTo(above);
+  } else {
+    masm->CheckCharacterGT(border - 1, above);
+  }
+}
+
+
+static void EmitDoubleBoundaryTest(RegExpMacroAssembler* masm,
+                                   int first,
+                                   int last,
+                                   Label* fall_through,
+                                   Label* even_label,

[ulan, 2012/03/28 13:14:08]

Odd/even doesn't make sense without the ranges2 array. Consider something like
in_range, out_of_range.

[Erik Corry, 2012/03/29 14:48:59]

Done.

+                                   Label* odd_label) {
+  if (even_label == fall_through) {
+    if (first == last) {
+      masm->CheckNotCharacter(first, odd_label);
+    } else {
+      masm->CheckCharacterNotInRange(first, last, odd_label);
+    }
+  } else {
+    if (first == last) {
+      masm->CheckCharacter(first, even_label);
+    } else {
+      masm->CheckCharacterInRange(first, last, even_label);
+    }
+    if (odd_label != fall_through) masm->GoTo(odd_label);
+  }
+}
+
+

[ulan, 2012/03/28 13:14:08]

A comment about odd/even/ranges2 would be helpful here.
If I understand correctly there is also an implicit precondition on values in
ranges2:
for all i, j: (ranges2[i] >> kTableSizeBits) == (ranges[j] >> kTableSizeBits).

[Erik Corry, 2012/03/29 14:48:59]

Done.

+static void EmitUseLookupTable(
+    RegExpMacroAssembler* masm,
+    ZoneList<int>* ranges2,
+    int start_index,
+    int end_index,
+    int min_char,
+    Label* fall_through,
+    Label* even_label,
+    Label* odd_label) {
+  static const int kSize = RegExpMacroAssembler::kTableSize;
+  static const int kMask = RegExpMacroAssembler::kTableMask;
+
+  char templ[kSize];
+  Label* on_bit_set;
+  Label* on_bit_clear;
+  int bit;
+  if (even_label == fall_through) {
+    on_bit_set = odd_label;
+    on_bit_clear = even_label;
+    bit = 1;
+  } else {
+    on_bit_set = even_label;
+    on_bit_clear = odd_label;
+    bit = 0;
+  }
+  int base = (min_char & ~kMask);
+  for (int i = 0; i < (ranges2->at(start_index) & kMask) && i < kSize; i++) {
+    templ[i] = bit;
+  }
+  int j = 0;
+  bit ^= 1;
+  for (int i = start_index; i < end_index; i++) {
+    for (j = (ranges2->at(i) & kMask);
+         j < ranges2->at(i + 1) - base && j < kSize;

[ulan, 2012/03/28 13:14:08]

Is (ranges2->at(i + 1) - base) == ranges2->at(i + 1) & kMask?
If yes, I would prefer the kMask version because it is consistent with j
initializer.
If not, I don't understand this part.

[Erik Corry, 2012/03/29 14:48:59]

The answer is yes, and it is changed to use the kMask version.

+         j++) {
+      templ[j] = bit;
+    }
+    bit ^= 1;
+  }
+  for (int i = j; i < kSize; i++) {
+    templ[i] = bit;
+  }
+  // TODO(erikcorry): Cache these.
+  Handle<ByteArray> ba = FACTORY->NewByteArray(kSize, TENURED);
+  for (int i = 0; i < kSize; i++) {
+    ba->set(i, templ[i]);
+  }
+  masm->CheckBitInTable(ba, on_bit_set);
+  if (on_bit_clear != fall_through) masm->GoTo(on_bit_clear);
+}
+
+
+// Gets a series of segments representing a character class.  If the character

[ulan, 2012/03/28 13:14:08]

Gets a series of segment boundaries ...

[Erik Corry, 2012/03/29 14:48:59]

Done.

+// is in the range between  even and an odd boundary (counting from start_index)
+// then go to even_label, otherwise go to odd_label.  We already know that
+// the character is in the range of min_char to max_char inclusive.  Either
+// label can be NULL indicating backtracking.  Either label can also be equal to
+// the fall_through label.
+static void GenerateBranches(RegExpMacroAssembler* masm,
+                             ZoneList<int>* ranges2,
+                             int start_index,
+                             int end_index,
+                             uc16 min_char,
+                             uc16 max_char,
+                             Label* fall_through,
+                             Label* even_label,
+                             Label* odd_label) {
+  int first = ranges2->at(start_index);
+  int last = ranges2->at(end_index) - 1;
+
+  // Just need to test if the character is before or on-or-after
+  // a particular character.
+  if (start_index == end_index) {
+    EmitBoundaryTest(masm, first, fall_through, even_label, odd_label);
+    return;
+  }
+
+  // Another almost trivial case:  There is one interval in the middle that is
+  // different from the end intervals.
+  if (start_index + 1 == end_index) {
+    EmitDoubleBoundaryTest(
+        masm, first, last, fall_through, even_label, odd_label);
+    return;
+  }
+
+  // It's not worth using table lookup if there are very few intervals in the
+  // character class.
+  if (end_index - start_index <= 6) {
+    typedef enum { kSingleCharacter, kRange, kDone } SearchOrder;
+    // It is faster to test for individual characters, so we look for those
+    // first, then try arbitrary ranges in the second round.
+    for (SearchOrder step = kSingleCharacter;
+         step < kDone;
+         step = (step == kSingleCharacter) ? kRange : kDone) {
+      for (int i = start_index; i < end_index; i++) {
+        int c = ranges2->at(i);

[ulan, 2012/03/28 13:14:08]

If you extract the body of the loop into a function, then you could avoid
SearchOrder trickery:
1. Search for a single char range.
2. If found, call the function on this char range.
3. Otherwise, call the function on the first range.

[Erik Corry, 2012/03/29 14:48:59]

Done.

+        int next = ranges2->at(i + 1) - 1;
+        if (step == kRange || c == next) {
+          bool odd = (((i - start_index) & 1) == 1);
+          Label* in_range_label = odd ? odd_label : even_label;
+          Label rest;

[ulan, 2012/03/28 13:14:08]

'fall_through' seems to be a better name than 'rest'.

[Erik Corry, 2012/03/29 14:48:59]

Renamed to dummy since it is not actually used.

+          EmitDoubleBoundaryTest(masm, c, next, &rest, in_range_label, &rest);
+          ASSERT(!rest.is_linked());
+          // Cut out the single range by rewriting the array.

[ulan, 2012/03/28 13:14:08]

This implicitly creates a new range with endpoints ranges2[i-1] .. ranges2[i+2].
A comment that it preserves the oddity of the labels would be helpful.

[Erik Corry, 2012/03/29 14:48:59]

Done.

+          for (int j = i; j > start_index; j--) {
+            ranges2->at(j) = ranges2->at(j - 1);
+          }
+          for (int j = i + 1; j < end_index; j++) {
+            ranges2->at(j) = ranges2->at(j + 1);
+          }
+          GenerateBranches(masm,

[ulan, 2012/03/28 13:14:08]

I think start_index + 1 can be larger that end_index - 1, but GenerateBranches
doesn't handle it.

[Erik Corry, 2012/03/29 14:48:59]

We do not get into this if() unless they are 6 apart.
Assert added.

+                           ranges2,
+                           start_index + 1,
+                           end_index - 1,
+                           min_char,
+                           max_char,
+                           fall_through,
+                           even_label,
+                           odd_label);
+          return;
+        }
+      }
+    }
+    UNREACHABLE();
+  }
+
+  // If there are a lot of intervals in the regexp, then we will use tables to
+  // determine whether the character is inside or outside the character class.
+  static const int kBits = RegExpMacroAssembler::kTableSizeBits;
+  static const int kSize = RegExpMacroAssembler::kTableSize;
+  static const int kMask = RegExpMacroAssembler::kTableMask;
+
+  if ((max_char >> kBits) == (min_char >> kBits)) {
+    EmitUseLookupTable(masm,
+                       ranges2,
+                       start_index,
+                       end_index,
+                       min_char,
+                       fall_through,
+                       even_label,
+                       odd_label);
+  } else {
+    if ((min_char >> kBits) != (first >> kBits)) {
+      masm->CheckCharacterLT(first, odd_label);
+      GenerateBranches(masm,
+                       ranges2,
+                       start_index + 1,
+                       end_index,
+                       first,
+                       max_char,
+                       fall_through,
+                       odd_label,
+                       even_label);
+      return;
+    }
+
+    // Unicode case.  Split the search space into kSize spaces that are handled
+    // with recursion.
+    int new_start_index = start_index;
+    int border = (first & ~kMask) + kSize;
+    while (new_start_index <= end_index) {
+      if (ranges2->at(new_start_index) > border) break;

[ulan, 2012/03/28 13:14:08]

I would expect to break on >=

[Erik Corry, 2012/03/29 14:48:59]

I think this is correct.  If there is a border right on the edge we want to cut
right before the border, but we don't want the new start_index to be on the
border, since that would make a trivial zero-width range at the start.

+      new_start_index++;
+    }
+    // new_start_index is the index of the first edge that is beyond the
+    // current kSize space.
+
+    // For very large search spaces we do a binary chop search of the non-ASCII
+    // space instead of just going to the end of the current kSize space.  The
+    // heuristics are complicated a little by the fact that any 128-character
+    // encoding space can be quickly tested with a table lookup, so we don't
+    // wish to do binary chop search at a smaller granularity than that.  A
+    // 128-character space can take up a lot of space in the ranges2 array if,
+    // for example, we only want to match every second character (eg. the lower
+    // case characters on some Unicode pages).
+    int binary_chop_index = (end_index + start_index) / 2;

[ulan, 2012/03/28 13:14:08]

Why not (end_index + new_start_index) / 2 ?

[Erik Corry, 2012/03/29 14:48:59]

If we are doing binary chop then we would want to do it exactly in the middle,
but new_start_index is one page higher than the middle.

+    if (border - 1 > String::kMaxAsciiCharCode &&

[ulan, 2012/03/28 13:14:08]

border >= String::kMaxAsciiCharCode

[Erik Corry, 2012/03/29 14:48:59]

This line makes a cut at the ASCII non-ASCII boundary because the ASCII area is
so important for performance.  Even a Cyrillic text like the Hippo article on
todays Russian Wikipedia front page is 20% ASCII.  In order to bypass the binary
chop branch tree for ASCII this is the correct test.  Comment added, though it
does not explicitly mention the Hippo.

+        end_index - start_index > (new_start_index - start_index) * 4 &&
+        last - first > kSize * 4 &&

[ulan, 2012/03/28 13:14:08]

Are 4s above magic?

[Erik Corry, 2012/03/29 14:48:59]

Yes.  I changed it to 2, which makes little difference to performance, but makes
more sense (there's no difference between binary chop and just one at a time
when there are only two pages left).

+        binary_chop_index > new_start_index &&
+        ranges2->at(binary_chop_index) > first + 2 * kSize) {
+      int scan_forward_for_section_border = binary_chop_index;;
+      int new_border = (ranges2->at(binary_chop_index) | kMask) + 1;
+      while (scan_forward_for_section_border < end_index) {

[ulan, 2012/03/28 13:14:08]

This loop construct appears twice. Maybe put it into a separate function?

[Erik Corry, 2012/03/29 14:48:59]

The two occurrences are slightly different.  A function that has 7 lines of body
and returns two values will have much bigger overhead, and given that they are
not doing exactly the same I can't see a nice way to do it.

+        if (ranges2->at(scan_forward_for_section_border) > new_border) {
+          new_start_index = scan_forward_for_section_border;
+          border = new_border;
+          break;
+        }
+        scan_forward_for_section_border++;
+      }
+    }
+
+    ASSERT(new_start_index > start_index);
+    Label handle_rest;
+    Label* above = &handle_rest;
+    int new_end_index = new_start_index - 1;
+    if (new_start_index > end_index) {
+      // We didn't find any section that started after the limit, so everything
+      // above the border is one of the terminal labels.
+      above = (end_index & 1) != (start_index & 1) ? odd_label : even_label;
+    }
+    if (ranges2->at(new_end_index) == border) {
+      new_end_index--;
+    }

[ulan, 2012/03/28 13:14:08]

Can we extract the code above into a separate function that returns a
new_start_index and a border? There are many edge cases, I would be happy if
those would be unit tested.

[Erik Corry, 2012/03/29 14:48:59]

Extracted, and more tests added.  It's fuzzing rather than unit, but it improves
the coverage and caught an off-by-one error.

+    masm->CheckCharacterGT(border - 1, above);
+    Label dummy;
+    GenerateBranches(masm,
+                     ranges2,
+                     start_index,
+                     new_end_index,
+                     min_char,
+                     border - 1,
+                     &dummy,
+                     even_label,
+                     odd_label);
+    if (handle_rest.is_linked()) {
+      masm->Bind(&handle_rest);
+      bool flip = (new_start_index & 1) != (start_index & 1);
+      GenerateBranches(masm,
+                       ranges2,
+                       new_start_index,
+                       end_index,
+                       border,
+                       max_char,
+                       &dummy,
+                       flip ? odd_label : even_label,
+                       flip ? even_label : odd_label);
+    }
+  }
+}
+
+
 static void EmitCharClass(RegExpMacroAssembler* macro_assembler,
                           RegExpCharacterClass* cc,
                           bool ascii,
                           Label* on_failure,
                           int cp_offset,
                           bool check_offset,
                           bool preloaded) {
   ZoneList<CharacterRange>* ranges = cc->ranges();
+  if (!CharacterRange::IsCanonical(ranges)) {
+    CharacterRange::Canonicalize(ranges);
+  }
+
   int max_char;
   if (ascii) {
     max_char = String::kMaxAsciiCharCode;
   } else {
     max_char = String::kMaxUtf16CodeUnit;
   }
 
-  Label success;
-
-  Label* char_is_in_class =
-      cc->is_negated() ? on_failure : &success;
-
   int range_count = ranges->length();
 
   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);
     }
     if (check_offset) {
       macro_assembler->CheckPosition(cp_offset, on_failure);
     }
     return;
   }
 
   if (last_valid_range == 0 &&
+      ranges->at(0).IsEverything(max_char)) {
+    if (cc->is_negated()) {
+      macro_assembler->GoTo(on_failure);
+    } else {
+      // This is a common case hit by non-anchored expressions.
+      if (check_offset) {
+        macro_assembler->CheckPosition(cp_offset, on_failure);
+      }
+    }
+    return;
+  }
+  if (last_valid_range == 0 &&
       !cc->is_negated() &&
       ranges->at(0).IsEverything(max_char)) {
     // This is a common case hit by non-anchored expressions.
     if (check_offset) {
       macro_assembler->CheckPosition(cp_offset, on_failure);
     }
     return;
   }
 
   if (!preloaded) {
     macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check_offset);
   }
 
   if (cc->is_standard() &&
         macro_assembler->CheckSpecialCharacterClass(cc->standard_type(),
                                                     on_failure)) {
       return;
   }
 
-  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);
-      }
-      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);
+
+  // A new list with ascending entries.  Each entry is a code unit
+  // where there is a boundary between code units that are part of
+  // the class and code units that are not.  Normally we insert an
+  // entry at zero which goes to the failure label, but if there
+  // was already one there we fall through for success on that entry.
+  // Subsequent entries have alternating meaning (success/failure).
+  ZoneList<int>* ranges2 =

[ulan, 2012/03/28 13:14:08]

This fits into one line. Can we find a better name than 'ranges2'? How about
'range_endpoints', 'range_points', 'range_boundaries', 'alternating_ranges'.

[Erik Corry, 2012/03/29 14:48:59]

range_boundaries, but I changed it to just ranges inside most of the other
functions because anything longer will cause cascading reformats to stay within
80 columns.

+      new ZoneList<int>(last_valid_range);
+
+  bool zeroth_entry_is_failure = true;
+  if (cc->is_negated()) zeroth_entry_is_failure = false;

[ulan, 2012/03/28 13:14:08]

zeroth_entry_is_failure = !cc->is_negated();

[Erik Corry, 2012/03/29 14:48:59]

Done.

+
+  int start = ranges->at(0).from();
+  if (start == 0) {
+    zeroth_entry_is_failure = !zeroth_entry_is_failure;
+  } else {
+    ranges2->Add(0);

[ulan, 2012/03/28 13:14:08]

I wonder why we need ranges2[0] to be zero? GenerateBranch doens't seem to rely
on ranges2[0] == 0 and uses min_char. 

[Erik Corry, 2012/03/29 14:48:59]

Done.

   }
 
-  CharacterRange& range = ranges->at(last_valid_range);
-  uc16 from = range.from();
-  uc16 to = range.to();
+  for (int i = 0; i <= last_valid_range; i++) {
+    CharacterRange& range = ranges->at(i);
+    ranges2->Add(range.from());
+    ranges2->Add(range.to() + 1);
+  }
+  int ranges2_length = ranges2->length() - 1;

[ulan, 2012/03/28 13:14:08]

In 'ranges2_length' the 'length' suffix is misleading. I think it is not a
length but an index, so it should be called something like 'end_index'.

[Erik Corry, 2012/03/29 14:48:59]

Done.

+  if (ranges2->at(ranges2_length) >= max_char) ranges2_length--;
 
-  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);
-      } else {
-        macro_assembler->CheckCharacterLT(from, on_failure);
-      }
-    }
-    if (to != String::kMaxUtf16CodeUnit) {
-      if (cc->is_negated()) {
-        macro_assembler->CheckCharacterLT(to + 1, on_failure);
-      } else {
-        macro_assembler->CheckCharacterGT(to, on_failure);
-      }
-    } else {
-      if (cc->is_negated()) {
-        macro_assembler->GoTo(on_failure);
-      }
-    }
-  }
-  macro_assembler->Bind(&success);
+  Label fall_through;
+  GenerateBranches(macro_assembler,
+                   ranges2,
+                   1,
+                   ranges2_length,
+                   0,
+                   max_char,
+                   &fall_through,
+                   zeroth_entry_is_failure ? &fall_through : on_failure,
+                   zeroth_entry_is_failure ? on_failure : &fall_through);
+  macro_assembler->Bind(&fall_through);
 }
 
 
 RegExpNode::~RegExpNode() {
 }
 
 
 RegExpNode::LimitResult RegExpNode::LimitVersions(RegExpCompiler* compiler,
                                                   Trace* trace) {
   // If we are generating a greedy loop then don't stop and don't reuse code.
@@ skipping 3666 matching lines @@
   }
 
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal