Port and integrate the irregexp engine from V8

runtime/vm/regexp.h

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_REGEXP_H_
 #define VM_REGEXP_H_
 
 #include "vm/assembler.h"
+#include "vm/intermediate_language.h"
 #include "vm/object.h"
+#include "vm/regexp_assembler.h"
 
 namespace dart {
 
 // Forward declarations.
 class AlternativeGeneration;
 class BoyerMooreLookahead;
 class NodeVisitor;
 class QuickCheckDetails;
 class RegExpAtom;
 class RegExpCharacterClass;
@@ skipping 212 matching lines @@
   // this case anchored branches will always fail and can be ignored when
   // determining how many characters are consumed on success.
   virtual intptr_t EatsAtLeast(intptr_t still_to_find, intptr_t budget,
                                bool not_at_start) = 0;
   // Emits some quick code that checks whether the preloaded characters match.
   // Falls through on certain failure, jumps to the label on possible success.
   // If the node cannot make a quick check it does nothing and returns false.
   bool EmitQuickCheck(RegExpCompiler* compiler,
                       Trace* trace,
                       bool preload_has_checked_bounds,
-                      Label* on_possible_success,
+                      BlockLabel* on_possible_success,
                       QuickCheckDetails* details_return,
                       bool fall_through_on_failure);
   // For a given number of characters this returns a mask and a value.  The
   // next n characters are anded with the mask and compared with the value.
   // A comparison failure indicates the node cannot match the next n characters.
   // A comparison success indicates the node may match.
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     intptr_t characters_filled_in,
                                     bool not_at_start) = 0;
@@ skipping 39 matching lines @@
   }
 
   // We want to avoid recalculating the lookahead info, so we store it on the
   // node.  Only info that is for this node is stored.  We can tell that the
   // info is for this node when offset == 0, so the information is calculated
   // relative to this node.
   void SaveBMInfo(BoyerMooreLookahead* bm, bool not_at_start, intptr_t offset) {
     if (offset == 0) set_bm_info(not_at_start, bm);
   }
 
-  Label* label() { return &label_; }
+  BlockLabel* label() { return &label_; }
   // If non-generic code is generated for a node (i.e. the node is not at the
   // start of the trace) then it cannot be reused.  This variable sets a limit
   // on how often we allow that to happen before we insist on starting a new
   // trace and generating generic code for a node that can be reused by flushing
   // the deferred actions in the current trace and generating a goto.
   static const intptr_t kMaxCopiesCodeGenerated = 10;
 
   NodeInfo* info() { return &info_; }
 
   BoyerMooreLookahead* bm_info(bool not_at_start) {
     return bm_info_[not_at_start ? 1 : 0];
   }
 
   Isolate* isolate() const { return isolate_; }
 
  protected:
   enum LimitResult { DONE, CONTINUE };
   RegExpNode* replacement_;
 
+  LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace);
+
   void set_bm_info(bool not_at_start, BoyerMooreLookahead* bm) {
     bm_info_[not_at_start ? 1 : 0] = bm;
   }
 
  private:
   static const intptr_t kFirstCharBudget = 10;
-  Label label_;
+  BlockLabel label_;
   NodeInfo info_;
   // This variable keeps track of how many times code has been generated for
   // this node (in different traces).  We don't keep track of where the
   // generated code is located unless the code is generated at the start of
   // a trace, in which case it is generic and can be reused by flushing the
   // deferred operations in the current trace and generating a goto.
   intptr_t trace_count_;
   BoyerMooreLookahead* bm_info_[2];
   Isolate* isolate_;
 };
@@ skipping 189 matching lines @@
   RegExpNode* node_;
   ZoneGrowableArray<Guard*>* guards_;
 };
 
 
 // A set of unsigned integers that behaves especially well on small
 // integers (< 32).  May do zone-allocation.
 class OutSet: public ZoneAllocated {
  public:
   OutSet() : first_(0), remaining_(NULL), successors_(NULL) { }
-  OutSet* Extend(unsigned value, Zone* zone);
+  OutSet* Extend(unsigned value, Isolate* isolate);
   bool Get(unsigned value) const;
   static const unsigned kFirstLimit = 32;
 
  private:
   // Destructively set a value in this set.  In most cases you want
   // to use Extend instead to ensure that only one instance exists
   // that contains the same values.
-  void Set(unsigned value, Zone* zone);
+  void Set(unsigned value, Isolate* isolate);
 
   // The successors are a list of sets that contain the same values
   // as this set and the one more value that is not present in this
   // set.
   ZoneGrowableArray<OutSet*>* successors() { return successors_; }
 
   OutSet(uint32_t first, ZoneGrowableArray<unsigned>* remaining)
       : first_(first), remaining_(remaining), successors_(NULL) { }
   uint32_t first_;
   ZoneGrowableArray<unsigned>* remaining_;
   ZoneGrowableArray<OutSet*>* successors_;
   friend class Trace;
 };
 
 
 // A mapping from integers, specified as ranges, to a set of integers.
 // Used for mapping character ranges to choices.
 class DispatchTable : public ZoneAllocated {
  public:
   DispatchTable() { }
 
   class Entry {
    public:
     Entry() : from_(0), to_(0), out_set_(NULL) { }
     Entry(uint16_t from, uint16_t to, OutSet* out_set)
         : from_(from), to_(to), out_set_(out_set) { }
     uint16_t from() { return from_; }
     uint16_t to() { return to_; }
     void set_to(uint16_t value) { to_ = value; }
-    void AddValue(intptr_t value, Zone* zone) {
-      out_set_ = out_set_->Extend(value, zone);
+    void AddValue(intptr_t value, Isolate* isolate) {
+      out_set_ = out_set_->Extend(value, isolate);
     }
     OutSet* out_set() { return out_set_; }
    private:
     uint16_t from_;
     uint16_t to_;
     OutSet* out_set_;
   };
 
   class Config {
    public:
@@ skipping 391 matching lines @@
   Position positions_[4];
   // These values are the condensate of the above array after Rationalize().
   uint32_t mask_;
   uint32_t value_;
   // If set to true, there is no way this quick check can match at all.
   // E.g., if it requires to be at the start of the input, and isn't.
   bool cannot_match_;
 };
 
 
+// Improve the speed that we scan for an initial point where a non-anchored
+// regexp can match by using a Boyer-Moore-like table. This is done by
+// identifying non-greedy non-capturing loops in the nodes that eat any
+// character one at a time.  For example in the middle of the regexp
+// /foo[\s\S]*?bar/ we find such a loop.  There is also such a loop implicitly
+// inserted at the start of any non-anchored regexp.
+//
+// When we have found such a loop we look ahead in the nodes to find the set of
+// characters that can come at given distances. For example for the regexp
+// /.?foo/ we know that there are at least 3 characters ahead of us, and the
+// sets of characters that can occur are [any, [f, o], [o]]. We find a range in
+// the lookahead info where the set of characters is reasonably constrained. In
+// our example this is from index 1 to 2 (0 is not constrained). We can now
+// look 3 characters ahead and if we don't find one of [f, o] (the union of
+// [f, o] and [o]) then we can skip forwards by the range size (in this case 2).
+//
+// For Unicode input strings we do the same, but modulo 128.
+//
+// We also look at the first string fed to the regexp and use that to get a hint
+// of the character frequencies in the inputs. This affects the assessment of
+// whether the set of characters is 'reasonably constrained'.
+//
+// We also have another lookahead mechanism (called quick check in the code),
+// which uses a wide load of multiple characters followed by a mask and compare
+// to determine whether a match is possible at this point.
+enum ContainedInLattice {
+  kNotYet = 0,
+  kLatticeIn = 1,
+  kLatticeOut = 2,
+  kLatticeUnknown = 3  // Can also mean both in and out.
+};
+
+
+inline ContainedInLattice Combine(ContainedInLattice a, ContainedInLattice b) {
+  return static_cast<ContainedInLattice>(a | b);
+}
+
+
+ContainedInLattice AddRange(ContainedInLattice a,
+                            const int* ranges,
+                            intptr_t ranges_size,
+                            Interval new_range);
+
+
+class BoyerMoorePositionInfo : public ZoneAllocated {
+ public:
+  explicit BoyerMoorePositionInfo(Isolate* isolate)
+      : map_(new(isolate) ZoneGrowableArray<bool>(kMapSize)),
+        map_count_(0),
+        w_(kNotYet),
+        s_(kNotYet),
+        d_(kNotYet),
+        surrogate_(kNotYet) {
+     for (intptr_t i = 0; i < kMapSize; i++) {
+       map_->Add(false);
+     }
+  }
+
+  bool& at(intptr_t i) { return map_->At(i); }
+
+  static const intptr_t kMapSize = 128;
+  static const intptr_t kMask = kMapSize - 1;
+
+  intptr_t map_count() const { return map_count_; }
+
+  void Set(intptr_t character);
+  void SetInterval(const Interval& interval);
+  void SetAll();
+  bool is_non_word() { return w_ == kLatticeOut; }
+  bool is_word() { return w_ == kLatticeIn; }
+
+ private:
+  ZoneGrowableArray<bool>* map_;
+  intptr_t map_count_;  // Number of set bits in the map.
+  ContainedInLattice w_;  // The \w character class.
+  ContainedInLattice s_;  // The \s character class.
+  ContainedInLattice d_;  // The \d character class.
+  ContainedInLattice surrogate_;  // Surrogate UTF-16 code units.
+};
+
+
+class BoyerMooreLookahead : public ZoneAllocated{
+ public:
+  BoyerMooreLookahead(intptr_t length, RegExpCompiler* compiler,
+                      Isolate* Isolate);
+
+  intptr_t length() { return length_; }
+  intptr_t max_char() { return max_char_; }
+  RegExpCompiler* compiler() { return compiler_; }
+
+  intptr_t Count(intptr_t map_number) {
+    return bitmaps_->At(map_number)->map_count();
+  }
+
+  BoyerMoorePositionInfo* at(intptr_t i) { return bitmaps_->At(i); }
+
+  void Set(intptr_t map_number, intptr_t character) {
+    if (character > max_char_) return;
+    BoyerMoorePositionInfo* info = bitmaps_->At(map_number);
+    info->Set(character);
+  }
+
+  void SetInterval(intptr_t map_number, const Interval& interval) {
+    if (interval.from() > max_char_) return;
+    BoyerMoorePositionInfo* info = bitmaps_->At(map_number);
+    if (interval.to() > max_char_) {
+      info->SetInterval(Interval(interval.from(), max_char_));
+    } else {
+      info->SetInterval(interval);
+    }
+  }
+
+  void SetAll(intptr_t map_number) {
+    bitmaps_->At(map_number)->SetAll();
+  }
+
+  void SetRest(intptr_t from_map) {
+    for (intptr_t i = from_map; i < length_; i++) SetAll(i);
+  }
+  bool EmitSkipInstructions(RegExpMacroAssembler* masm);
+
+ private:
+  // This is the value obtained by EatsAtLeast.  If we do not have at least this
+  // many characters left in the sample string then the match is bound to fail.
+  // Therefore it is OK to read a character this far ahead of the current match
+  // point.
+  intptr_t length_;
+  RegExpCompiler* compiler_;
+  // 0x7f for ASCII, 0xffff for UTF-16.
+  intptr_t max_char_;
+  ZoneGrowableArray<BoyerMoorePositionInfo*>* bitmaps_;
+
+  intptr_t GetSkipTable(intptr_t min_lookahead,
+                   intptr_t max_lookahead,

[ricow1, 2014/09/05 05:49:58]

indentation 

[jgruber1, 2014/09/05 06:17:25]

Done.

+                   TypedData* boolean_skip_table);
+  bool FindWorthwhileInterval(int* from, int* to);
+  intptr_t FindBestInterval(
+      intptr_t max_number_of_chars,
+      intptr_t old_biggest_points,
+      int* from, int* to);
+};
+
+
 // There are many ways to generate code for a node.  This class encapsulates
 // the current way we should be generating.  In other words it encapsulates
 // the current state of the code generator.  The effect of this is that we
 // generate code for paths that the matcher can take through the regular
 // expression.  A given node in the regexp can be code-generated several times
 // as it can be part of several traces.  For example for the regexp:
 // /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part
 // of the foo-bar-baz trace and once as part of the foo-ip-baz trace.  The code
 // to match foo is generated only once (the traces have a common prefix).  The
 // code to store the capture is deferred and generated (twice) after the places
@@ skipping 95 matching lines @@
            cp_offset_ == 0 &&
            characters_preloaded_ == 0 &&
            bound_checked_up_to_ == 0 &&
            quick_check_performed_.characters() == 0 &&
            at_start_ == UNKNOWN;
   }
   TriBool at_start() { return at_start_; }
   void set_at_start(bool at_start) {
     at_start_ = at_start ? TRUE_VALUE : FALSE_VALUE;
   }
-  Label* backtrack() { return backtrack_; }
-  Label* loop_label() { return loop_label_; }
+  BlockLabel* backtrack() { return backtrack_; }
+  BlockLabel* loop_label() { return loop_label_; }
   RegExpNode* stop_node() { return stop_node_; }
   intptr_t characters_preloaded() { return characters_preloaded_; }
   intptr_t bound_checked_up_to() { return bound_checked_up_to_; }
   intptr_t flush_budget() { return flush_budget_; }
   QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
   bool mentions_reg(intptr_t reg);
   // Returns true if a deferred position store exists to the specified
   // register and stores the offset in the out-parameter.  Otherwise
   // returns false.
   bool GetStoredPosition(intptr_t reg, intptr_t* cp_offset);
   // These set methods and AdvanceCurrentPositionInTrace should be used only on
   // new traces - the intention is that traces are immutable after creation.
   void add_action(DeferredAction* new_action) {
     ASSERT(new_action->next_ == NULL);
     new_action->next_ = actions_;
     actions_ = new_action;
   }
-  void set_backtrack(Label* backtrack) { backtrack_ = backtrack; }
+  void set_backtrack(BlockLabel* backtrack) { backtrack_ = backtrack; }
   void set_stop_node(RegExpNode* node) { stop_node_ = node; }
-  void set_loop_label(Label* label) { loop_label_ = label; }
+  void set_loop_label(BlockLabel* label) { loop_label_ = label; }
   void set_characters_preloaded(intptr_t count) {
     characters_preloaded_ = count;
   }
   void set_bound_checked_up_to(intptr_t to) { bound_checked_up_to_ = to; }
   void set_flush_budget(intptr_t to) { flush_budget_ = to; }
   void set_quick_check_performed(QuickCheckDetails* d) {
     quick_check_performed_ = *d;
   }
   void InvalidateCurrentCharacter();
   void AdvanceCurrentPositionInTrace(intptr_t by, RegExpCompiler* compiler);
 
  private:
-  intptr_t FindAffectedRegisters(OutSet* affected_registers, Zone* zone);
+  intptr_t FindAffectedRegisters(OutSet* affected_registers, Isolate* isolate);
   void PerformDeferredActions(RegExpMacroAssembler* macro,
                               intptr_t max_register,
                               const OutSet& affected_registers,
                               OutSet* registers_to_pop,
                               OutSet* registers_to_clear,
-                              Zone* zone);
+                              Isolate* isolate);
   void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
                                 intptr_t max_register,
                                 const OutSet& registers_to_pop,
                                 const OutSet& registers_to_clear);
   intptr_t cp_offset_;
   DeferredAction* actions_;
-  Label* backtrack_;
+  BlockLabel* backtrack_;
   RegExpNode* stop_node_;
-  Label* loop_label_;
+  BlockLabel* loop_label_;
   intptr_t characters_preloaded_;
   intptr_t bound_checked_up_to_;
   QuickCheckDetails quick_check_performed_;
   intptr_t flush_budget_;
   TriBool at_start_;
 };
 
 
 class NodeVisitor : public ValueObject {
  public:
@@ skipping 64 matching lines @@
   bool contains_anchor;
   String& error;
   intptr_t capture_count;
 };
 
 
 class RegExpEngine: public AllStatic {
  public:
   struct CompilationResult {
     explicit CompilationResult(const char* error_message)
-        : error_message(error_message),
-          num_registers(0) {}
-    CompilationResult(Object* code, intptr_t registers)
-      : error_message(NULL),
-        num_registers(registers) {}
+        : function(Function::Handle()),
+          error_message(error_message) {}
+    explicit CompilationResult(const Function& function)
+      : function(function),
+        error_message(NULL) {}
+
+    const Function& function;
     const char* error_message;
-    intptr_t num_registers;
   };
 
   static CompilationResult Compile(RegExpCompileData* input,
                                    bool ignore_case,
                                    bool global,
                                    bool multiline,
                                    const String& pattern,
                                    const String& sample_subject,
                                    bool is_ascii);
 
+  static RawJSRegExp* New(const String& pattern,
+                          bool multi_line,
+                          bool ignore_case);
+
   static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 }  // namespace dart
 
 #endif  // VM_REGEXP_H_