Character classes

src/jsregexp.h

 // 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 108 matching lines @@
   // subject JS String object is cached in the heap.  We also cache a
   // translation between position and utf8 position.
   static char* utf8_subject_cache_;
   static int utf8_length_cache_;
   static int utf8_position_;
   static int character_position_;
 };
 
 
 template <typename Char> class RegExpNode;
+class CharacterClassAllocator;
+
+
+class CharacterClass {
+ public:
+
+  enum Type { EMPTY = 0, FIELD = 1, RANGES = 2, UNION = 3 };
+
+  // A closed range from and including 'from', to and including 'to'.
+  class Range {
+   public:
+    Range() : from_(0), to_(0) { }
+    Range(uc16 from, uc16 to) : from_(from), to_(to) { ASSERT(from <= to); }
+    uc16 from() { return from_; }
+    uc16 to() { return to_; }
+   private:
+    uc16 from_;
+    uc16 to_;
+  };
+
+  CharacterClass() : type_(EMPTY) { }
+
+  explicit CharacterClass(Type type) : type_(type) { }
+
+  bool Contains(uc16 c);
+
+  // Returns a character class with a single bit set
+  static inline CharacterClass SingletonField(uc16 chr);
+
+  // Returns a bitfield character class with a closed range set.  The
+  // range must fit within one field, that is, fit between two adjacent
+  // kFieldMax-aligned boundaries.
+  static inline CharacterClass RangeField(Range range);
+
+  static inline CharacterClass Union(CharacterClass* left,
+                                     CharacterClass* right);
+
+  // Initializes an empty charclass as a bitfield containing the
+  // specified ranges.
+  void InitializeFieldFrom(Vector<Range> ranges);
+
+  // Initializes this character class to be the specified ranges.
+  // This class must be empty.
+  void InitializeRangesFrom(Vector<Range> ranges,
+                            CharacterClassAllocator* alloc);
+
+  // Creates a new character class containing the specified ranges
+  // and allocating any sub-classes using the specified allocator.
+  static CharacterClass Ranges(Vector<Range> boundaries,
+                               CharacterClassAllocator* alloc);
+
+  // Returns one of the built-in character classes such as '\w' or
+  // '\S'.
+  static CharacterClass* GetCharacterClass(uc16 tag);
+
+  inline void write_nibble(int index, byte value);
+  inline byte read_nibble(int index);
+
+  static inline unsigned segment_of(uc16 value);
+  static inline uc16 segment_start(unsigned segment);
+
+ private:
+  static const int kCharSize = 16;
+  static const int kFieldSegmentIndexWidth = 10;
+  static const int kFieldSegmentWidth = kCharSize - kFieldSegmentIndexWidth;

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

Isn't this the field width, not the segment width?
(It's used to compute the kFieldMax).

+  static const int kFieldMax = (1 << kFieldSegmentWidth);
+  static const int kSegmentMask = (1 << kFieldSegmentWidth) - 1;
+  static const int kNibbleCount = kFieldMax / 4;
+  STATIC_ASSERT(kFieldMax == 8 * sizeof(uint64_t));
+
+  Type type() { return type_; }
+
+  static inline uint64_t long_bit(int index) {
+    return static_cast<uint64_t>(1) << index;
+  }
+
+  Type type_: 2;
+  unsigned segment_ : 10;
+  unsigned count_ : 4;
+  union {
+    // These have the same type to make it easier to change one without
+    // touching the other.
+    uint64_t u_field;
+    uint64_t u_ranges;
+    struct {
+      CharacterClass* left;
+      CharacterClass* right;
+    } u_union;

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

Slightly confusing name to have for a struct (especially inside a union). Can't
think of more appropriate one, though.

+  } data_;
+};
+
+
+STATIC_ASSERT(sizeof(CharacterClass) == 3 * kIntSize);
+
+
+class CharacterClassAllocator {
+ public:
+  virtual CharacterClass* Allocate() = 0;
+  virtual ~CharacterClassAllocator() { }
+};
+
+
+template <int kCount>
+class StaticCharacterClassAllocator: public CharacterClassAllocator {
+ public:
+  StaticCharacterClassAllocator() : used_(0) { }
+  virtual CharacterClass* Allocate();
+ private:
+  int used_;
+  CharacterClass preallocated_[kCount];
+};
 
 
 class RegExpEngine: public AllStatic {
  public:
   template <typename Char>
   static RegExpNode<Char>* Compile(RegExpTree* regexp);
 
   template <typename Char>
   static bool Execute(RegExpNode<Char>* start, Vector<Char> input);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_