[regexp] implement character classes for unicode regexps.

src/regexp/jsregexp.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_REGEXP_JSREGEXP_H_
 #define V8_REGEXP_JSREGEXP_H_
 
 #include "src/allocation.h"
 #include "src/assembler.h"
 #include "src/regexp/regexp-ast.h"
@@ skipping 247 matching lines @@
 
 // A mapping from integers, specified as ranges, to a set of integers.
 // Used for mapping character ranges to choices.
 class DispatchTable : public ZoneObject {
  public:
   explicit DispatchTable(Zone* zone) : tree_(zone) { }
 
   class Entry {
    public:
     Entry() : from_(0), to_(0), out_set_(NULL) { }
-    Entry(uc16 from, uc16 to, OutSet* out_set)
-        : from_(from), to_(to), out_set_(out_set) { }
-    uc16 from() { return from_; }
-    uc16 to() { return to_; }
-    void set_to(uc16 value) { to_ = value; }
+    Entry(uc32 from, uc32 to, OutSet* out_set)
+        : from_(from), to_(to), out_set_(out_set) {}
+    uc32 from() { return from_; }
+    uc32 to() { return to_; }
+    void set_to(uc32 value) { to_ = value; }
     void AddValue(int value, Zone* zone) {
       out_set_ = out_set_->Extend(value, zone);
     }
     OutSet* out_set() { return out_set_; }
    private:
-    uc16 from_;
-    uc16 to_;
+    uc32 from_;
+    uc32 to_;
     OutSet* out_set_;
   };
 
   class Config {
    public:
-    typedef uc16 Key;
+    typedef uc32 Key;
     typedef Entry Value;
-    static const uc16 kNoKey;
+    static const uc32 kNoKey;
     static const Entry NoValue() { return Value(); }
-    static inline int Compare(uc16 a, uc16 b) {
+    static inline int Compare(uc32 a, uc32 b) {
       if (a == b)
         return 0;
       else if (a < b)
         return -1;
       else
         return 1;
     }
   };
 
   void AddRange(CharacterRange range, int value, Zone* zone);
-  OutSet* Get(uc16 value);
+  OutSet* Get(uc32 value);
   void Dump();
 
   template <typename Callback>
   void ForEach(Callback* callback) {
     return tree()->ForEach(callback);
   }
 
  private:
   // There can't be a static empty set since it allocates its
   // successors in a zone and caches them.
   OutSet* empty() { return &empty_; }
   OutSet empty_;
   ZoneSplayTree<Config>* tree() { return &tree_; }
   ZoneSplayTree<Config> tree_;
 };
 
 
+// Categorizes character ranges into BMP, non-BMP, lead, and trail surrogates.
+class UnicodeRangeSplitter {
+ public:
+  UnicodeRangeSplitter(Zone* zone, ZoneList<CharacterRange>* base);
+  void Call(uc32 from, DispatchTable::Entry entry);
+
+  ZoneList<CharacterRange>* bmp() { return bmp_; }
+  ZoneList<CharacterRange>* lead_surrogates() { return lead_surrogates_; }
+  ZoneList<CharacterRange>* trail_surrogates() { return trail_surrogates_; }
+  ZoneList<CharacterRange>* non_bmp() const { return non_bmp_; }
+
+ private:
+  static const int kBase = 0;
+  // Separate ranges into
+  static const int kBmpCodePoints = 1;
+  static const int kLeadSurrogates = 2;
+  static const int kTrailSurrogates = 3;
+  static const int kNonBmpCodePoints = 4;
+
+  Zone* zone_;
+  DispatchTable table_;
+  ZoneList<CharacterRange>* bmp_;
+  ZoneList<CharacterRange>* lead_surrogates_;
+  ZoneList<CharacterRange>* trail_surrogates_;
+  ZoneList<CharacterRange>* non_bmp_;
+};
+
+
 #define FOR_EACH_NODE_TYPE(VISIT)                                    \
   VISIT(End)                                                         \
   VISIT(Action)                                                      \
   VISIT(Choice)                                                      \
   VISIT(BackReference)                                               \
   VISIT(Assertion)                                                   \
   VISIT(Text)
 
 
 class Trace;
@@ skipping 355 matching lines @@
   TextNode(ZoneList<TextElement>* elms, bool read_backward,
            RegExpNode* on_success)
       : SeqRegExpNode(on_success), elms_(elms), read_backward_(read_backward) {}
   TextNode(RegExpCharacterClass* that, bool read_backward,
            RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         elms_(new (zone()) ZoneList<TextElement>(1, zone())),
         read_backward_(read_backward) {
     elms_->Add(TextElement::CharClass(that), zone());
   }
+  // Create TextNode for a single character class for the given ranges.
+  static TextNode* CreateForCharacterRanges(Zone* zone,
+                                            ZoneList<CharacterRange>* ranges,
+                                            bool read_backward,
+                                            RegExpNode* on_success);
+  // Create TextNode for a surrogate pair with a range given for the
+  // lead and the trail surrogate each.
+  static TextNode* CreateForSurrogatePair(Zone* zone, CharacterRange lead,
+                                          CharacterRange trail,
+                                          bool read_backward,
+                                          RegExpNode* on_success);
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start);
   ZoneList<TextElement>* elements() { return elms_; }
   bool read_backward() { return read_backward_; }
   void MakeCaseIndependent(Isolate* isolate, bool is_one_byte);
@@ skipping 103 matching lines @@
  private:
   int start_reg_;
   int end_reg_;
   bool read_backward_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
-  explicit EndNode(Action action, Zone* zone)
-      : RegExpNode(zone), action_(action) { }
+  EndNode(Action action, Zone* zone) : RegExpNode(zone), action_(action) {}
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find,
                           int recursion_depth,
                           bool not_at_start) { return 0; }
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start) {
     // Returning 0 from EatsAtLeast should ensure we never get here.
@@ skipping 670 matching lines @@
           code(isolate->heap()->the_hole_value()),
           num_registers(0) {}
     CompilationResult(Object* code, int registers)
         : error_message(NULL), code(code), num_registers(registers) {}
     const char* error_message;
     Object* code;
     int num_registers;
   };
 
   static CompilationResult Compile(Isolate* isolate, Zone* zone,
-                                   RegExpCompileData* input, bool ignore_case,
-                                   bool global, bool multiline, bool sticky,
+                                   RegExpCompileData* input,
+                                   JSRegExp::Flags flags,
                                    Handle<String> pattern,
                                    Handle<String> sample_subject,
                                    bool is_one_byte);
 
   static bool TooMuchRegExpCode(Handle<String> pattern);
 
   static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 
@@ skipping 18 matching lines @@
   static const int kStringOffset = 0;
   static const int kPatternOffset = 1;
   static const int kArrayOffset = 2;
   static const int kLastMatchOffset = 3;
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGEXP_JSREGEXP_H_