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 37 matching lines @@
         table_(NULL),
         not_at_start_(false),
         being_calculated_(false) { }
   virtual void Accept(NodeVisitor* visitor);
   void AddAlternative(GuardedAlternative node) {
     alternatives()->Add(node);
   }
   ZoneGrowableArray<GuardedAlternative>* alternatives() {
     return alternatives_;
   }
-  DispatchTable* GetTable(bool ignore_case);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual intptr_t EatsAtLeast(intptr_t still_to_find, intptr_t budget,
                                bool not_at_start);
   intptr_t EatsAtLeastHelper(intptr_t still_to_find,
                              intptr_t budget,
                              RegExpNode* ignore_this_node,
                              bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     intptr_t characters_filled_in,
@@ skipping 333 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_)[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,
+                        TypedData* boolean_skip_table);
+  bool FindWorthwhileInterval(intptr_t* from, intptr_t* to);
+  intptr_t FindBestInterval(
+      intptr_t max_number_of_chars,
+      intptr_t old_biggest_points,
+      intptr_t* from, intptr_t* 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 43 matching lines @@
 
  private:
   bool ignore_case_;
   bool is_ascii_;
   const char* error_message_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
 };
 
 
-struct RegExpCompileData {
+struct RegExpCompileData : public ZoneAllocated {
   RegExpCompileData()
     : tree(NULL),
       node(NULL),
       simple(true),
       contains_anchor(false),
       error(String::Handle(String::null())),
       capture_count(0) { }
   RegExpTree* tree;
   RegExpNode* node;
   bool simple;
   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) {}
+        : macro_assembler(NULL),
+          graph_entry(NULL),
+          num_blocks(-1),
+          num_stack_locals(-1),
+          error_message(error_message) {}
+    explicit CompilationResult(IRRegExpMacroAssembler* macro_assembler,

[Vyacheslav Egorov (Google), 2014/10/01 20:13:21]

No need to mark multiple arguments constructor "explicit"

[jgruber1, 2014/10/03 18:59:51]

Done.

+                               GraphEntryInstr* graph_entry,
+                               intptr_t num_blocks,
+                               intptr_t num_stack_locals)
+      : macro_assembler(macro_assembler),
+        graph_entry(graph_entry),
+        num_blocks(num_blocks),
+        num_stack_locals(num_stack_locals),
+        error_message(NULL) {}
+
+    IRRegExpMacroAssembler* macro_assembler;
+    GraphEntryInstr* graph_entry;
+    const intptr_t num_blocks;
+    const intptr_t num_stack_locals;
+
     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 CompilationResult Compile(
+      RegExpCompileData* input,
+      const ParsedFunction* parsed_function,
+      ZoneGrowableArray<const ICData*>* ic_data_array);
+
+  static RawJSRegExp* New(Isolate* isolate,
+                          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_