VM: Re-format to use at most one newline between functions

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 RUNTIME_VM_REGEXP_H_
 #define RUNTIME_VM_REGEXP_H_
 
 #include "vm/assembler.h"
+#include "vm/flow_graph_compiler.h"
 #include "vm/intermediate_language.h"
-#include "vm/flow_graph_compiler.h"
 #include "vm/object.h"
 #include "vm/regexp_assembler.h"
 
 namespace dart {
 
 class NodeVisitor;
 class RegExpCompiler;
 class RegExpMacroAssembler;
 class RegExpNode;
 class RegExpTree;
 class BoyerMooreLookahead;
 
-
 // Represents code units in the range from from_ to to_, both ends are
 // inclusive.
 class CharacterRange {
  public:
   CharacterRange() : from_(0), to_(0) {}
   CharacterRange(uint16_t from, uint16_t to) : from_(from), to_(to) {}
 
   static void AddClassEscape(uint16_t type,
                              ZoneGrowableArray<CharacterRange>* ranges);
   static GrowableArray<const intptr_t> GetWordBounds();
@@ skipping 37 matching lines @@
   static const intptr_t kStartMarker = (1 << 24);
   static const intptr_t kPayloadMask = (1 << 24) - 1;
 
  private:
   uint16_t from_;
   uint16_t to_;
 
   DISALLOW_ALLOCATION();
 };
 
-
 // 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);
   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);
 
   // 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;
 };
 
-
 #define FOR_EACH_NODE_TYPE(VISIT)                                              \
   VISIT(End)                                                                   \
   VISIT(Action)                                                                \
   VISIT(Choice)                                                                \
   VISIT(BackReference)                                                         \
   VISIT(Assertion)                                                             \
   VISIT(Text)
 
-
 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT)                                      \
   VISIT(Disjunction)                                                           \
   VISIT(Alternative)                                                           \
   VISIT(Assertion)                                                             \
   VISIT(CharacterClass)                                                        \
   VISIT(Atom)                                                                  \
   VISIT(Quantifier)                                                            \
   VISIT(Capture)                                                               \
   VISIT(Lookahead)                                                             \
   VISIT(BackReference)                                                         \
   VISIT(Empty)                                                                 \
   VISIT(Text)
 
-
 #define FORWARD_DECLARE(Name) class RegExp##Name;
 FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE)
 #undef FORWARD_DECLARE
 
-
 class TextElement {
  public:
   enum TextType { ATOM, CHAR_CLASS };
 
   static TextElement Atom(RegExpAtom* atom);
   static TextElement CharClass(RegExpCharacterClass* char_class);
 
   intptr_t cp_offset() const { return cp_offset_; }
   void set_cp_offset(intptr_t cp_offset) { cp_offset_ = cp_offset; }
   intptr_t length() const;
@@ skipping 16 matching lines @@
   TextElement(TextType text_type, RegExpTree* tree)
       : cp_offset_(-1), text_type_(text_type), tree_(tree) {}
 
   intptr_t cp_offset_;
   TextType text_type_;
   RegExpTree* tree_;
 
   DISALLOW_ALLOCATION();
 };
 
-
 class Trace;
 struct PreloadState;
 class GreedyLoopState;
 class AlternativeGenerationList;
 
 struct NodeInfo {
   NodeInfo()
       : being_analyzed(false),
         been_analyzed(false),
         follows_word_interest(false),
@@ skipping 46 matching lines @@
   // character was.
   bool follows_word_interest : 1;
   bool follows_newline_interest : 1;
   bool follows_start_interest : 1;
 
   bool at_end : 1;
   bool visited : 1;
   bool replacement_calculated : 1;
 };
 
-
 // Details of a quick mask-compare check that can look ahead in the
 // input stream.
 class QuickCheckDetails {
  public:
   QuickCheckDetails()
       : characters_(0), mask_(0), value_(0), cannot_match_(false) {}
   explicit QuickCheckDetails(intptr_t characters)
       : characters_(characters), mask_(0), value_(0), cannot_match_(false) {}
   bool Rationalize(bool one_byte);
   // Merge in the information from another branch of an alternation.
@@ skipping 27 matching lines @@
   // 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_;
 
   DISALLOW_ALLOCATION();
 };
 
-
 class RegExpNode : public ZoneAllocated {
  public:
   explicit RegExpNode(Zone* zone)
       : replacement_(NULL), trace_count_(0), zone_(zone) {
     bm_info_[0] = bm_info_[1] = NULL;
   }
   virtual ~RegExpNode();
   virtual void Accept(NodeVisitor* visitor) = 0;
   // Generates a goto to this node or actually generates the code at this point.
   virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0;
@@ skipping 107 matching lines @@
   // 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];
   Zone* zone_;
 };
 
-
 // A simple closed interval.
 class Interval {
  public:
   Interval() : from_(kNone), to_(kNone) {}
   Interval(intptr_t from, intptr_t to) : from_(from), to_(to) {}
 
   Interval Union(Interval that) {
     if (that.from_ == kNone)
       return *this;
     else if (from_ == kNone)
@@ skipping 11 matching lines @@
   static Interval Empty() { return Interval(); }
   static const intptr_t kNone = -1;
 
  private:
   intptr_t from_;
   intptr_t to_;
 
   DISALLOW_ALLOCATION();
 };
 
-
 class SeqRegExpNode : public RegExpNode {
  public:
   explicit SeqRegExpNode(RegExpNode* on_success)
       : RegExpNode(on_success->zone()), on_success_(on_success) {}
   RegExpNode* on_success() { return on_success_; }
   void set_on_success(RegExpNode* node) { on_success_ = node; }
   virtual RegExpNode* FilterOneByte(intptr_t depth, bool ignore_case);
   virtual void FillInBMInfo(intptr_t offset,
                             intptr_t budget,
                             BoyerMooreLookahead* bm,
                             bool not_at_start) {
     on_success_->FillInBMInfo(offset, budget - 1, bm, not_at_start);
     if (offset == 0) set_bm_info(not_at_start, bm);
   }
 
  protected:
   RegExpNode* FilterSuccessor(intptr_t depth, bool ignore_case);
 
  private:
   RegExpNode* on_success_;
 };
 
-
 class ActionNode : public SeqRegExpNode {
  public:
   enum ActionType {
     SET_REGISTER,
     INCREMENT_REGISTER,
     STORE_POSITION,
     BEGIN_SUBMATCH,
     POSITIVE_SUBMATCH_SUCCESS,
     EMPTY_MATCH_CHECK,
     CLEAR_CAPTURES
@@ skipping 68 matching lines @@
       intptr_t range_from;
       intptr_t range_to;
     } u_clear_captures;
   } data_;
   ActionNode(ActionType action_type, RegExpNode* on_success)
       : SeqRegExpNode(on_success), action_type_(action_type) {}
   ActionType action_type_;
   friend class DotPrinter;
 };
 
-
 class TextNode : public SeqRegExpNode {
  public:
   TextNode(ZoneGrowableArray<TextElement>* elms, RegExpNode* on_success)
       : SeqRegExpNode(on_success), elms_(elms) {}
   TextNode(RegExpCharacterClass* that, RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         elms_(new (zone()) ZoneGrowableArray<TextElement>(1)) {
     elms_->Add(TextElement::CharClass(that));
   }
   virtual void Accept(NodeVisitor* visitor);
@@ skipping 31 matching lines @@
   void TextEmitPass(RegExpCompiler* compiler,
                     TextEmitPassType pass,
                     bool preloaded,
                     Trace* trace,
                     bool first_element_checked,
                     intptr_t* checked_up_to);
   intptr_t Length();
   ZoneGrowableArray<TextElement>* elms_;
 };
 
-
 class AssertionNode : public SeqRegExpNode {
  public:
   enum AssertionType {
     AT_END,
     AT_START,
     AT_BOUNDARY,
     AT_NON_BOUNDARY,
     AFTER_NEWLINE
   };
   static AssertionNode* AtEnd(RegExpNode* on_success) {
@@ skipping 30 matching lines @@
   void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace);
   enum IfPrevious { kIsNonWord, kIsWord };
   void BacktrackIfPrevious(RegExpCompiler* compiler,
                            Trace* trace,
                            IfPrevious backtrack_if_previous);
   AssertionNode(AssertionType t, RegExpNode* on_success)
       : SeqRegExpNode(on_success), assertion_type_(t) {}
   AssertionType assertion_type_;
 };
 
-
 class BackReferenceNode : public SeqRegExpNode {
  public:
   BackReferenceNode(intptr_t start_reg,
                     intptr_t end_reg,
                     RegExpNode* on_success)
       : SeqRegExpNode(on_success), start_reg_(start_reg), end_reg_(end_reg) {}
   virtual void Accept(NodeVisitor* visitor);
   intptr_t start_register() { return start_reg_; }
   intptr_t end_register() { return end_reg_; }
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual intptr_t EatsAtLeast(intptr_t still_to_find,
                                intptr_t recursion_depth,
                                bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     intptr_t characters_filled_in,
                                     bool not_at_start) {
     return;
   }
   virtual void FillInBMInfo(intptr_t offset,
                             intptr_t budget,
                             BoyerMooreLookahead* bm,
                             bool not_at_start);
 
  private:
   intptr_t start_reg_;
   intptr_t end_reg_;
 };
 
-
 class EndNode : public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
   explicit EndNode(Action action, Zone* zone)
       : RegExpNode(zone), action_(action) {}
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual intptr_t EatsAtLeast(intptr_t still_to_find,
                                intptr_t recursion_depth,
                                bool not_at_start) {
@@ skipping 11 matching lines @@
                             BoyerMooreLookahead* bm,
                             bool not_at_start) {
     // Returning 0 from EatsAtLeast should ensure we never get here.
     UNREACHABLE();
   }
 
  private:
   Action action_;
 };
 
-
 class NegativeSubmatchSuccess : public EndNode {
  public:
   NegativeSubmatchSuccess(intptr_t stack_pointer_reg,
                           intptr_t position_reg,
                           intptr_t clear_capture_count,
                           intptr_t clear_capture_start,
                           Zone* zone)
       : EndNode(NEGATIVE_SUBMATCH_SUCCESS, zone),
         stack_pointer_register_(stack_pointer_reg),
         current_position_register_(position_reg),
         clear_capture_count_(clear_capture_count),
         clear_capture_start_(clear_capture_start) {}
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
 
  private:
   intptr_t stack_pointer_register_;
   intptr_t current_position_register_;
   intptr_t clear_capture_count_;
   intptr_t clear_capture_start_;
 };
 
-
 class Guard : public ZoneAllocated {
  public:
   enum Relation { LT, GEQ };
   Guard(intptr_t reg, Relation op, intptr_t value)
       : reg_(reg), op_(op), value_(value) {}
   intptr_t reg() { return reg_; }
   Relation op() { return op_; }
   intptr_t value() { return value_; }
 
  private:
   intptr_t reg_;
   Relation op_;
   intptr_t value_;
 };
 
-
 class GuardedAlternative {
  public:
   explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) {}
   void AddGuard(Guard* guard, Zone* zone);
   RegExpNode* node() { return node_; }
   void set_node(RegExpNode* node) { node_ = node; }
   ZoneGrowableArray<Guard*>* guards() { return guards_; }
 
  private:
   RegExpNode* node_;
   ZoneGrowableArray<Guard*>* guards_;
 
   DISALLOW_ALLOCATION();
 };
 
-
 struct AlternativeGeneration;
 
-
 class ChoiceNode : public RegExpNode {
  public:
   explicit ChoiceNode(intptr_t expected_size, Zone* zone)
       : RegExpNode(zone),
         alternatives_(new (zone)
                           ZoneGrowableArray<GuardedAlternative>(expected_size)),
         not_at_start_(false),
         being_calculated_(false) {}
   virtual void Accept(NodeVisitor* visitor);
   void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
@@ skipping 59 matching lines @@
                    AlternativeGenerationList* alt_gens,
                    intptr_t first_choice,
                    Trace* trace,
                    PreloadState* preloads);
   // If true, this node is never checked at the start of the input.
   // Allows a new trace to start with at_start() set to false.
   bool not_at_start_;
   bool being_calculated_;
 };
 
-
 class NegativeLookaheadChoiceNode : public ChoiceNode {
  public:
   explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail,
                                        GuardedAlternative then_do_this,
                                        Zone* zone)
       : ChoiceNode(2, zone) {
     AddAlternative(this_must_fail);
     AddAlternative(then_do_this);
   }
   virtual intptr_t EatsAtLeast(intptr_t still_to_find,
@@ skipping 15 matching lines @@
   // alternative that is expected to fail.  This is because quick check code
   // starts by loading enough characters for the alternative that takes fewest
   // characters, but on a negative lookahead the negative branch did not take
   // part in that calculation (EatsAtLeast) so the assumptions don't hold.
   virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
     return !is_first;
   }
   virtual RegExpNode* FilterOneByte(intptr_t depth, bool ignore_case);
 };
 
-
 class LoopChoiceNode : public ChoiceNode {
  public:
   explicit LoopChoiceNode(bool body_can_be_zero_length, Zone* zone)
       : ChoiceNode(2, zone),
         loop_node_(NULL),
         continue_node_(NULL),
         body_can_be_zero_length_(body_can_be_zero_length) {}
   void AddLoopAlternative(GuardedAlternative alt);
   void AddContinueAlternative(GuardedAlternative alt);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
@@ skipping 20 matching lines @@
   // goes back to the node itself.
   void AddAlternative(GuardedAlternative node) {
     ChoiceNode::AddAlternative(node);
   }
 
   RegExpNode* loop_node_;
   RegExpNode* continue_node_;
   bool body_can_be_zero_length_;
 };
 
-
 // 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
@@ skipping 12 matching lines @@
 // 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 intptr_t* ranges,
                             intptr_t ranges_size,
                             Interval new_range);
 
-
 class BoyerMoorePositionInfo : public ZoneAllocated {
  public:
   explicit BoyerMoorePositionInfo(Zone* zone)
       : map_(new (zone) ZoneGrowableArray<bool>(kMapSize)),
         map_count_(0),
         w_(kNotYet),
         s_(kNotYet),
         d_(kNotYet),
         surrogate_(kNotYet) {
     for (intptr_t i = 0; i < kMapSize; i++) {
@@ skipping 16 matching lines @@
 
  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, Zone* Zone);
 
   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();
@@ skipping 39 matching lines @@
   intptr_t GetSkipTable(intptr_t min_lookahead,
                         intptr_t max_lookahead,
                         const 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 152 matching lines @@
   BlockLabel* loop_label_;
   intptr_t characters_preloaded_;
   intptr_t bound_checked_up_to_;
   QuickCheckDetails quick_check_performed_;
   intptr_t flush_budget_;
   TriBool at_start_;
 
   DISALLOW_ALLOCATION();
 };
 
-
 class GreedyLoopState {
  public:
   explicit GreedyLoopState(bool not_at_start);
 
   BlockLabel* label() { return &label_; }
   Trace* counter_backtrack_trace() { return &counter_backtrack_trace_; }
 
  private:
   BlockLabel label_;
   Trace counter_backtrack_trace_;
 };
 
-
 struct PreloadState {
   static const intptr_t kEatsAtLeastNotYetInitialized = -1;
   bool preload_is_current_;
   bool preload_has_checked_bounds_;
   intptr_t preload_characters_;
   intptr_t eats_at_least_;
   void init() { eats_at_least_ = kEatsAtLeastNotYetInitialized; }
 
   DISALLOW_ALLOCATION();
 };
 
-
 class NodeVisitor : public ValueObject {
  public:
   virtual ~NodeVisitor() {}
 #define DECLARE_VISIT(Type) virtual void Visit##Type(Type##Node* that) = 0;
   FOR_EACH_NODE_TYPE(DECLARE_VISIT)
 #undef DECLARE_VISIT
   virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); }
 };
 
-
 // Assertion propagation moves information about assertions such as
 // \b to the affected nodes.  For instance, in /.\b./ information must
 // be propagated to the first '.' that whatever follows needs to know
 // if it matched a word or a non-word, and to the second '.' that it
 // has to check if it succeeds a word or non-word.  In this case the
 // result will be something like:
 //
 //   +-------+        +------------+
 //   |   .   |        |      .     |
 //   +-------+  --->  +------------+
@@ skipping 20 matching lines @@
   void fail(const char* error_message) { error_message_ = error_message; }
 
  private:
   bool ignore_case_;
   bool is_one_byte_;
   const char* error_message_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
 };
 
-
 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),
 #if !defined(DART_PRECOMPILED_RUNTIME)
           backtrack_goto(NULL),
           graph_entry(NULL),
           num_blocks(-1),
           num_stack_locals(-1),
@@ skipping 57 matching lines @@
                                  const String& pattern,
                                  bool multi_line,
                                  bool ignore_case);
 
   static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 }  // namespace dart
 
 #endif  // RUNTIME_VM_REGEXP_H_