Character classes

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 14 matching lines @@
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include <set>
 
 #include "v8.h"
 
 #include "ast.h"
 #include "execution.h"
 #include "factory.h"
-#include "jsregexp.h"
+#include "jsregexp-inl.h"
 #include "third_party/jscre/pcre.h"
 #include "platform.h"
 #include "runtime.h"
 #include "top.h"
 #include "compilation-cache.h"
 #include "string-stream.h"
 
 
 namespace v8 { namespace internal {
 
@@ skipping 767 matching lines @@
                                              void* rest) {
   ZoneList<RegExpTree*>* children = that->nodes();
   RegExpNode<Char>* current = static_cast<RegExpNode<Char>*>(rest);
   for (int i = children->length() - 1; i >= 0; i--) {
     current = Compile(children->at(i), current);
   }
   return current;
 }
 
 
+bool CharacterClass::Contains(uc16 c) {
+  switch (type()) {
+    case FIELD: {
+      int offset = segment_start(segment_);
+      if (c < offset) return false;
+      int index = c - offset;
+      if (index >= CharacterClass::kFieldMax) return false;
+      return (data_.u_field & long_bit(index)) != 0;
+    }
+    case RANGES: {
+      int offset = segment_start(segment_);
+      if (c < offset) return false;
+      bool is_on = false;
+      unsigned i = 0;
+      while (i < count_) {
+        int delta = 0;
+        int nibble = read_nibble(i);
+        int bit_offset = 0;
+        while ((nibble & 0x8) == 0) {
+          delta |= nibble << bit_offset;
+          bit_offset += 3;
+          nibble = read_nibble(++i);
+        }
+        delta |= (nibble & 0x7) << bit_offset;
+        i++;
+        offset += delta;
+        if (c < offset)
+          return is_on;
+        is_on = !is_on;
+      }
+      return false;
+    }
+    case UNION: {
+      return data_.u_union.left->Contains(c)
+          || data_.u_union.right->Contains(c);
+    }
+    default:
+      UNREACHABLE();
+      return false;
+  }
+}
+
+
+template <int kCount>
+CharacterClass* StaticCharacterClassAllocator<kCount>::Allocate() {
+  ASSERT(used_ < kCount);
+  CharacterClass* result = &preallocated_[used_];
+  used_++;
+  return result;
+}
+
+
+class StaticCharacterClasses {
+ public:
+  StaticCharacterClasses();
+  CharacterClass* GetClass(uc16 tag);
+  static StaticCharacterClasses* instance_;
+ private:
+  StaticCharacterClassAllocator<5> static_allocator_;
+  CharacterClass digit_;
+  CharacterClass whitespace_;
+  CharacterClass word_;
+};
+
+
+StaticCharacterClasses* StaticCharacterClasses::instance_ = NULL;
+
+
+StaticCharacterClasses::StaticCharacterClasses() {
+#define MAKE_CLASS(Name)\
+  CharacterClass::Ranges(Vector<CharacterClass::Range>(k##Name##Ranges,\
+                                                       k##Name##RangeCount), \
+                         &static_allocator_)
+
+  const int kDigitRangeCount = 1;
+  CharacterClass::Range kDigitRanges[kDigitRangeCount] = {
+    CharacterClass::Range('0', '9')
+  };
+  digit_ = MAKE_CLASS(Digit);
+
+  const int kWhiteSpaceRangeCount = 10;
+  CharacterClass::Range kWhiteSpaceRanges[kWhiteSpaceRangeCount] = {
+  CharacterClass::Range(0x0009, 0x0009), CharacterClass::Range(0x000B, 0x000C),
+  CharacterClass::Range(0x0020, 0x0020), CharacterClass::Range(0x00A0, 0x00A0),
+  CharacterClass::Range(0x1680, 0x1680), CharacterClass::Range(0x180E, 0x180E),
+  CharacterClass::Range(0x2000, 0x200A), CharacterClass::Range(0x202F, 0x202F),
+  CharacterClass::Range(0x205F, 0x205F), CharacterClass::Range(0x3000, 0x3000)
+  };
+  whitespace_ = MAKE_CLASS(WhiteSpace);
+
+  const int kWordRangeCount = 4;
+  static CharacterClass::Range kWordRanges[kWordRangeCount] = {
+    CharacterClass::Range('0', '9'), CharacterClass::Range('A', 'Z'),
+    CharacterClass::Range('_', '_'), CharacterClass::Range('a', 'z')
+  };
+  word_ = MAKE_CLASS(Word);
+
+#undef MAKE_CLASS
+}
+
+
+CharacterClass* StaticCharacterClasses::GetClass(uc16 tag) {
+  switch (tag) {
+    case 'd':
+      return &digit_;
+    case 's':
+      return &whitespace_;
+    case 'w':
+      return &word_;
+    default:
+      UNREACHABLE();
+      return NULL;
+  }
+}
+
+
+CharacterClass* CharacterClass::GetCharacterClass(uc16 tag) {
+  if (StaticCharacterClasses::instance_ == NULL)
+    StaticCharacterClasses::instance_ = new StaticCharacterClasses();
+  return StaticCharacterClasses::instance_->GetClass(tag);
+}
+
+
+CharacterClass CharacterClass::Ranges(Vector<Range> boundaries,
+                                      CharacterClassAllocator* alloc) {
+  CharacterClass result;
+  result.InitializeRangesFrom(boundaries, alloc);
+  return result;
+}
+
+
+void CharacterClass::InitializeFieldFrom(Vector<Range> boundaries) {
+  ASSERT(boundaries.length() > 0);
+  ASSERT_EQ(EMPTY, type_);
+  type_ = FIELD;
+  segment_ = segment_of(boundaries.first().from());
+  ASSERT_EQ(static_cast<int>(segment_),
+            static_cast<int>(segment_of(boundaries.last().to())));
+  data_.u_field = 0;
+  for (int i = 0; i < boundaries.length(); i++) {
+    int start = boundaries[i].from();
+    int end = boundaries[i].to();
+    // Mask in the range
+    uint64_t t0 = ~static_cast<uint64_t>(0) >> (63 - (end & kSegmentMask));
+    uint64_t t1 = ~static_cast<uint64_t>(0) << (start & kSegmentMask);
+    data_.u_field |= (t0 & t1);
+  }
+}
+
+
+void CharacterClass::InitializeRangesFrom(Vector<Range> boundaries,
+                                          CharacterClassAllocator* alloc) {
+  ASSERT(boundaries.length() > 0);
+  ASSERT_EQ(EMPTY, type_);
+  int start_segment = segment_of(boundaries.first().from());
+  int end_segment = segment_of(boundaries.last().to());
+  if (start_segment == end_segment) {
+    InitializeFieldFrom(boundaries);
+    return;
+  }
+  type_ = RANGES;
+  segment_ = start_segment;
+  data_.u_ranges = 0;
+  int offset = 0;
+  uc16 last_boundary = segment_start(segment_);
+  int i;
+  for (i = 0; i < boundaries.length(); i++) {
+    Range current = boundaries[i];
+    ASSERT(last_boundary <= current.from());
+    int word = current.from() - last_boundary;
+    // We have to repeat the write operation to write both the delta
+    // from the last range to the start of this one, and the delta
+    // from the start to the end of this range.
+    for (int j = 0; j < 2; j++) {
+      do {
+        if (offset >= 16)
+          goto overflow;
+        byte nibble = (word & 0x7);
+        int next_word = word >> 3;
+        if (next_word == 0)
+          nibble |= 0x8;
+        write_nibble(offset, nibble);
+        word = next_word;
+        offset++;
+      } while (word > 0);
+      word = current.to() - current.from() + 1;
+    }
+    count_ = offset;
+    last_boundary = current.to() + 1;
+    continue;
+   overflow:
+    CharacterClass* left = alloc->Allocate();
+    ASSERT(i > 0);
+    if (segment_of(boundaries[i-1].to()) == segment_) {
+      // If what we've written so far fits within a single segment we
+      // can fit it into a bitfield.
+      left->InitializeFieldFrom(boundaries.SubVector(0, i));

[Lasse Reichstein, 2008/10/30 10:28:42]

Try to read some more first, and see if more ranges fit into the same field.

+    } else {
+      // Otherwise we copy the work we've done so far into the left
+      // heap-allocated charclass.
+      *left = *this;

[Lasse Reichstein, 2008/10/30 10:28:42]

As discussed, the segments won't necessarily be disjoint if the next range are
in the same segment as the previous one.

+    }
+    CharacterClass* right = alloc->Allocate();
+    right->InitializeRangesFrom(boundaries.SubVector(i, boundaries.length()),
+                                alloc);
+    type_ = UNION;
+    data_.u_union.left = left;
+    data_.u_union.right = right;
+    return;
+  }
+}
+
+
 // -------------------------------------------------------------------
 // Execution
 
 
 template <typename Char>
 class ExecutionState {
  public:
   ExecutionState(RegExpNode<Char>* start, Vector<Char> input)
     : current_(start),
       input_(input),
@@ skipping 188 matching lines @@
 template
 bool RegExpEngine::Execute<const char>(RegExpNode<const char>* start,
                                        Vector<const char> input);
 
 template
 bool RegExpEngine::Execute<const uc16>(RegExpNode<const uc16>* start,
                                        Vector<const uc16> input);
 
 
 }}  // namespace v8::internal