runtime/vm/regexp/regexp-nodes.h

// Copyright 2019 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_REGEXP_NODES_H_
#define V8_REGEXP_REGEXP_NODES_H_

#include <algorithm>

#include "vm/regexp/label.h"
#include "vm/regexp/regexp-ast.h"
#include "vm/regexp/regexp.h"

namespace dart {

class AlternativeGenerationList;
class BoyerMooreLookahead;
class SpecialLoopState;
class NegativeSubmatchSuccess;
class NodeVisitor;
class QuickCheckDetails;
class RegExpCompiler;
class SeqRegExpNode;
class Trace;
template <typename T>
class RegExpNodePrinter;
struct PreloadState;
class RegExpMacroAssembler;

#define FOR_EACH_NODE_TYPE(VISIT)                                              \
  VISIT(End)                                                                   \
  VISIT(Action)                                                                \
  VISIT(Choice)                                                                \
  VISIT(LoopChoice)                                                            \
  VISIT(NegativeLookaroundChoice)                                              \
  VISIT(BackReference)                                                         \
  VISIT(Assertion)                                                             \
  VISIT(Text)

#define FORWARD_DECLARE(type) class type##Node;
FOR_EACH_NODE_TYPE(FORWARD_DECLARE)
#undef FORWARD_DECLARE

struct NodeInfo final {
  NodeInfo()
      : being_analyzed(false),
        been_analyzed(false),
        follows_word_interest(false),
        follows_newline_interest(false),
        follows_start_interest(false),
        at_end(false),
        visited(false),
        replacement_calculated(false) {}

  // Returns true if the interests and assumptions of this node
  // matches the given one.
  bool Matches(NodeInfo* that) {
    return (at_end == that->at_end) &&
           (follows_word_interest == that->follows_word_interest) &&
           (follows_newline_interest == that->follows_newline_interest) &&
           (follows_start_interest == that->follows_start_interest);
  }

  // Updates the interests of this node given the interests of the
  // node preceding it.
  void AddFromPreceding(NodeInfo* that) {
    at_end |= that->at_end;
    follows_word_interest |= that->follows_word_interest;
    follows_newline_interest |= that->follows_newline_interest;
    follows_start_interest |= that->follows_start_interest;
  }

  bool HasLookbehind() {
    return follows_word_interest || follows_newline_interest ||
           follows_start_interest;
  }

  // Sets the interests of this node to include the interests of the
  // following node.
  void AddFromFollowing(NodeInfo* that) {
    follows_word_interest |= that->follows_word_interest;
    follows_newline_interest |= that->follows_newline_interest;
    follows_start_interest |= that->follows_start_interest;
  }

  void ResetCompilationState() {
    being_analyzed = false;
    been_analyzed = false;
  }

  bool being_analyzed : 1;
  bool been_analyzed : 1;

  // These bits are set of this node has to know what the preceding
  // 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;
};

struct EatsAtLeastInfo final {
  EatsAtLeastInfo() : EatsAtLeastInfo(0) {}
  explicit EatsAtLeastInfo(uint8_t eats)
      : from_possibly_start(eats), from_not_start(eats) {}
  void SetMin(const EatsAtLeastInfo& other) {
    from_possibly_start =
        std::min(from_possibly_start, other.from_possibly_start);
    from_not_start = std::min(from_not_start, other.from_not_start);
  }
  void SetMax(int other) {
    uint8_t max = base::saturated_cast<uint8_t>(other);
    from_possibly_start = std::max(from_possibly_start, max);
    from_not_start = std::max(from_not_start, max);
  }

  bool IsZero() const {
    return from_possibly_start == 0 && from_not_start == 0;
  }

  // Any successful match starting from the current node will consume at least
  // this many characters. This does not necessarily mean that there is a
  // possible match with exactly this many characters, but we generally try to
  // get this number as high as possible to allow for early exit on failure.
  uint8_t from_possibly_start;

  // Like from_possibly_start, but with the additional assumption
  // that start-of-string assertions (^) can't match. This value is greater than
  // or equal to from_possibly_start.
  uint8_t from_not_start;
};

class EmitResult final {
 public:
  static EmitResult Success() { return EmitResult(kSuccess); }
  static EmitResult Error() { return EmitResult(kError); }

  bool IsSuccess() const { return result_ == kSuccess; }
  bool IsError() const { return result_ == kError; }

 private:
  enum Result { kSuccess, kError };
  constexpr explicit EmitResult(Result result) : result_(result) {}
  Result result_;
};

#define RETURN_IF_ERROR(stmt)                                                  \
  if (EmitResult r = (stmt); UNLIKELY(r.IsError())) return r

class RegExpNode : public ZoneObject {
 public:
  explicit RegExpNode(Zone* zone)
      : replacement_(nullptr),
        on_work_list_(false),
        trace_count_(0),
        zone_(zone) {
    bm_info_[0] = bm_info_[1] = nullptr;
  }
  virtual ~RegExpNode();
  virtual void Accept(NodeVisitor* visitor) = 0;
  // Generates a goto to this node or actually generates the code at this point.
  V8_WARN_UNUSED_RESULT virtual EmitResult Emit(RegExpCompiler* compiler,
                                                Trace* trace) = 0;
  // How many characters must this node consume at a minimum in order to
  // succeed.  The not_at_start argument is used to indicate that we know we are
  // not at the start of the input.  In this case anchored branches will always
  // fail and can be ignored when determining how many characters are consumed
  // on success.  If this node has not been analyzed yet, EatsAtLeast returns 0.
  uint32_t EatsAtLeast(bool not_at_start);
  static constexpr uint32_t kLargeEatsAtLeastValue = 255;
  // 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* bounds_check_trace,
                      Trace* trace,
                      bool preload_has_checked_bounds,
                      V8Label* on_possible_success,
                      QuickCheckDetails* details_return,
                      bool fall_through_on_failure,
                      ChoiceNode* predecessor);
  // 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.
  // TODO(pthier): Cache QuickCheckDetails to avoid recomputation.
  virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                    RegExpCompiler* compiler,
                                    int characters_filled_in,
                                    bool not_at_start,
                                    int budget) = 0;
  static const int kNodeIsTooComplexForFixedLengthLoops = kMinInt;
  virtual int FixedLengthLoopLength() {
    return kNodeIsTooComplexForFixedLengthLoops;
  }
  // Only returns the successor for a text node of length 1 that matches any
  // character and that has no guards on it.
  virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
      RegExpCompiler* compiler) {
    return nullptr;
  }

  // Collects information on the possible code units (mod 128) that can match if
  // we look forward.  This is used for a Boyer-Moore-like string searching
  // implementation.  TODO(erikcorry):  This should share more code with
  // EatsAtLeast, GetQuickCheckDetails.  The budget argument is used to limit
  // the number of nodes we are willing to look at in order to create this data.
  static const int kRecursionBudget = 200;
  bool KeepRecursing(RegExpCompiler* compiler);
  virtual void FillInBMInfo(Isolate* isolate,
                            int offset,
                            int budget,
                            BoyerMooreLookahead* bm,
                            bool not_at_start) {
    return;
  }

  // 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, int offset) {
    if (offset == 0) set_bm_info(not_at_start, bm);
  }

  V8Label* 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 int kMaxCopiesCodeGenerated = 10;

  bool on_work_list() { return on_work_list_; }
  void set_on_work_list(bool value) { on_work_list_ = value; }

  NodeInfo* info() { return &info_; }
  const EatsAtLeastInfo* eats_at_least_info() const { return &eats_at_least_; }
  void set_eats_at_least_info(const EatsAtLeastInfo& eats_at_least) {
    eats_at_least_ = eats_at_least;
  }

  // TODO(v8:10441): This is a hacky way to avoid exponential code size growth
  // for very large choice nodes that can be generated by unicode property
  // escapes. In order to avoid inlining (i.e. trace recursion), we pretend to
  // have generated the maximum count of code copies already.
  // We should instead fix this properly, e.g. by using the code size budget
  // (flush_budget) or by generating property escape matches as calls to a C
  // function.
  void SetDoNotInline() { trace_count_ = kMaxCopiesCodeGenerated; }

  BoyerMooreLookahead* bm_info(bool not_at_start) {
    return bm_info_[not_at_start ? 1 : 0];
  }

#define DECLARE_CAST(type)                                                     \
  virtual type##Node* As##type##Node() { return nullptr; }
  FOR_EACH_NODE_TYPE(DECLARE_CAST)
#undef DECLARE_CAST

  virtual NegativeSubmatchSuccess* AsNegativeSubmatchSuccess() {
    return nullptr;
  }
  virtual SeqRegExpNode* AsSeqRegExpNode() { return nullptr; }

  Zone* zone() const { return zone_; }

  virtual bool IsBacktrack() const { return false; }

 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 int kFirstCharBudget = 10;
  V8Label label_;
  bool on_work_list_;
  NodeInfo info_;

  // Saved values for EatsAtLeast results, to avoid recomputation. Filled in
  // during analysis (valid if info_.been_analyzed is true).
  EatsAtLeastInfo eats_at_least_;

  // 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.
  int trace_count_;
  BoyerMooreLookahead* bm_info_[2];

  Zone* zone_;
};

class SeqRegExpNode : public RegExpNode {
 public:
  explicit SeqRegExpNode(RegExpNode* on_success)
      : RegExpNode(on_success->zone()), on_success_(on_success) {}
  RegExpNode* on_success() const { return on_success_; }
  void set_on_success(RegExpNode* node) { on_success_ = node; }
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override {
    on_success_->FillInBMInfo(isolate, offset, budget - 1, bm, not_at_start);
    if (offset == 0) set_bm_info(not_at_start, bm);
  }
  SeqRegExpNode* AsSeqRegExpNode() override { return this; }

 private:
  RegExpNode* on_success_;
};

class ActionNode : public SeqRegExpNode {
 public:
  enum ActionType {
    SET_REGISTER_FOR_LOOP,
    INCREMENT_REGISTER,
    STORE_POSITION,
    RESTORE_POSITION,
    BEGIN_POSITIVE_SUBMATCH,
    BEGIN_NEGATIVE_SUBMATCH,
    POSITIVE_SUBMATCH_SUCCESS,
    EMPTY_MATCH_CHECK,
    CLEAR_CAPTURES,
    MODIFY_FLAGS,
    EATS_AT_LEAST,
  };
  static ActionNode* SetRegisterForLoop(int reg,
                                        int val,
                                        RegExpNode* on_success);
  static ActionNode* IncrementRegister(int reg, RegExpNode* on_success);
  static ActionNode* StorePosition(int reg, RegExpNode* on_success);
  static ActionNode* RestorePosition(int reg, RegExpNode* on_success);
  static ActionNode* ClearCaptures(Interval range, RegExpNode* on_success);
  static ActionNode* BeginPositiveSubmatch(int stack_pointer_reg,
                                           int position_reg,
                                           RegExpNode* body,
                                           ActionNode* success_node);
  static ActionNode* BeginNegativeSubmatch(int stack_pointer_reg,
                                           int position_reg,
                                           RegExpNode* on_success);
  static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg,
                                             int restore_reg,
                                             int clear_capture_count,
                                             int clear_capture_from,
                                             RegExpNode* on_success);
  static ActionNode* EmptyMatchCheck(int start_register,
                                     int repetition_register,
                                     int repetition_limit,
                                     RegExpNode* on_success);
  static ActionNode* ModifyFlags(RegExpFlags flags, RegExpNode* on_success);
  static ActionNode* EatsAtLeast(int characters, RegExpNode* on_success);
  ActionNode* AsActionNode() override { return this; }
  void Accept(NodeVisitor* visitor) override;
  V8_WARN_UNUSED_RESULT EmitResult Emit(RegExpCompiler* compiler,
                                        Trace* trace) override;
  void GetQuickCheckDetails(QuickCheckDetails* details,
                            RegExpCompiler* compiler,
                            int filled_in,
                            bool not_at_start,
                            int budget) override;
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override;
  ActionType action_type() const { return action_type_; }
  // TODO(erikcorry): We should allow some action nodes in fixed length loops.
  int FixedLengthLoopLength() override {
    return kNodeIsTooComplexForFixedLengthLoops;
  }
  RegExpFlags flags() const {
    DCHECK_EQ(action_type(), MODIFY_FLAGS);
    return RegExpFlags{data_.u_modify_flags.flags};
  }
  ActionNode* success_node() const {
    DCHECK_EQ(action_type(), BEGIN_POSITIVE_SUBMATCH);
    return data_.u_submatch.success_node;
  }
  int stored_eats_at_least() {
    DCHECK_EQ(action_type(), EATS_AT_LEAST);
    return data_.u_eats_at_least.characters;
  }

  bool Mentions(int reg) const {
    return base::IsInRange(reg, register_from(), register_to());
  }

  int value() const {
    ASSERT(action_type() == SET_REGISTER_FOR_LOOP);
    return data_.u_simple.value;
  }

  bool IsSimpleAction() const {
    return action_type() == STORE_POSITION ||
           action_type() == RESTORE_POSITION ||
           action_type() == INCREMENT_REGISTER ||
           action_type() == SET_REGISTER_FOR_LOOP ||
           action_type() == CLEAR_CAPTURES;
  }

  int register_from() const {
    ASSERT(IsSimpleAction());
    return data_.u_simple.register_from;
  }

  int register_to() const { return data_.u_simple.register_to; }

 protected:
  ActionNode(ActionType action_type, RegExpNode* on_success)
      : SeqRegExpNode(on_success), action_type_(action_type) {}

  ActionNode(ActionType action_type,
             RegExpNode* on_success,
             int from,
             int to = -1,
             int value = 0)
      : SeqRegExpNode(on_success), action_type_(action_type) {
    data_.u_simple.register_from = from;
    data_.u_simple.register_to = to == -1 ? from : to;
    data_.u_simple.value = value;
    ASSERT(IsSimpleAction());
  }

 private:
  union {
    struct {
      int register_from;
      int register_to;
      int value;
    } u_simple;
    struct {
      int stack_pointer_register;
      int current_position_register;
      int clear_register_count;
      int clear_register_from;
      ActionNode* success_node;  // Only used for positive submatch.
    } u_submatch;
    struct {
      int start_register;
      int repetition_register;
      int repetition_limit;
    } u_empty_match_check;
    struct {
      int flags;
    } u_modify_flags;
    struct {
      int characters;
    } u_eats_at_least;
  } data_;

  ActionType action_type_;
  friend class DotPrinterImpl;
  friend class RegExpNodePrinter<RegExpNode>;
  friend Zone;
};

class TextNode : public SeqRegExpNode {
 public:
  TextNode(ZoneList<TextElement>* elms,
           bool read_backward,
           RegExpNode* on_success)
      : SeqRegExpNode(on_success), elms_(elms), read_backward_(read_backward) {}
  TextNode(RegExpClassRanges* that, bool read_backward, RegExpNode* on_success)
      : SeqRegExpNode(on_success),
        elms_(zone()->New<ZoneList<TextElement>>(1, zone())),
        read_backward_(read_backward) {
    elms_->Add(TextElement::ClassRanges(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 (i.e. match a sequence of two uc16
  // code unit ranges).
  static TextNode* CreateForSurrogatePair(
      Zone* zone,
      CharacterRange lead,
      ZoneList<CharacterRange>* trail_ranges,
      bool read_backward,
      RegExpNode* on_success);
  static TextNode* CreateForSurrogatePair(Zone* zone,
                                          ZoneList<CharacterRange>* lead_ranges,
                                          CharacterRange trail,
                                          bool read_backward,
                                          RegExpNode* on_success);
  TextNode* AsTextNode() override { return this; }
  void Accept(NodeVisitor* visitor) override;
  V8_WARN_UNUSED_RESULT EmitResult Emit(RegExpCompiler* compiler,
                                        Trace* trace) override;
  void GetQuickCheckDetails(QuickCheckDetails* details,
                            RegExpCompiler* compiler,
                            int characters_filled_in,
                            bool not_at_start,
                            int budget) override;
  ZoneList<TextElement>* elements() { return elms_; }
  bool read_backward() const { return read_backward_; }
  void MakeCaseIndependent(Isolate* isolate,
                           bool is_one_byte,
                           RegExpFlags flags);
  int FixedLengthLoopLength() override;
  RegExpNode* GetSuccessorOfOmnivorousTextNode(
      RegExpCompiler* compiler) override;
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override;
  void CalculateOffsets();
  int Length();

  // Returns false if the text node can't match in one-byte mode.
  bool CanMatchLatin1(RegExpCompiler* compiler);

 private:
  enum TextEmitPassType {
    NON_LATIN1_MATCH,            // Check for characters that can never match.
    SIMPLE_CHARACTER_MATCH,      // Case-dependent single character check.
    NON_LETTER_CHARACTER_MATCH,  // Check characters that have no case equivs.
    CASE_CHARACTER_MATCH,        // Case-independent single character check.
    CHARACTER_CLASS_MATCH        // Character class.
  };
  void TextEmitPass(RegExpCompiler* compiler,
                    TextEmitPassType pass,
                    bool preloaded,
                    Trace* trace,
                    bool first_element_checked,
                    int* checked_up_to);
  ZoneList<TextElement>* elms_;
  bool read_backward_;
};

class AssertionNode : public SeqRegExpNode {
 public:
  enum AssertionType {
    AT_END,
    AT_START,
    AT_BOUNDARY,
    AT_NON_BOUNDARY,
    AFTER_NEWLINE
  };
  static AssertionNode* AtEnd(RegExpNode* on_success) {
    return on_success->zone()->New<AssertionNode>(AT_END, on_success);
  }
  static AssertionNode* AtStart(RegExpNode* on_success) {
    return on_success->zone()->New<AssertionNode>(AT_START, on_success);
  }
  static AssertionNode* AtBoundary(RegExpNode* on_success) {
    return on_success->zone()->New<AssertionNode>(AT_BOUNDARY, on_success);
  }
  static AssertionNode* AtNonBoundary(RegExpNode* on_success) {
    return on_success->zone()->New<AssertionNode>(AT_NON_BOUNDARY, on_success);
  }
  static AssertionNode* AfterNewline(RegExpNode* on_success) {
    return on_success->zone()->New<AssertionNode>(AFTER_NEWLINE, on_success);
  }
  AssertionNode* AsAssertionNode() override { return this; }
  void Accept(NodeVisitor* visitor) override;
  V8_WARN_UNUSED_RESULT EmitResult Emit(RegExpCompiler* compiler,
                                        Trace* trace) override;
  void GetQuickCheckDetails(QuickCheckDetails* details,
                            RegExpCompiler* compiler,
                            int filled_in,
                            bool not_at_start,
                            int budget) override;
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override;
  AssertionType assertion_type() const { return assertion_type_; }

 private:
  friend Zone;

  V8_WARN_UNUSED_RESULT EmitResult EmitBoundaryCheck(RegExpCompiler* compiler,
                                                     Trace* trace);
  enum IfPrevious { kIsNonWord, kIsWord };
  V8_WARN_UNUSED_RESULT EmitResult
  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(int start_reg,
                    int end_reg,
                    bool read_backward,
                    RegExpNode* on_success)
      : SeqRegExpNode(on_success),
        start_reg_(start_reg),
        end_reg_(end_reg),
        read_backward_(read_backward) {}
  BackReferenceNode* AsBackReferenceNode() override { return this; }
  void Accept(NodeVisitor* visitor) override;
  int start_register() const { return start_reg_; }
  int end_register() const { return end_reg_; }
  bool read_backward() const { return read_backward_; }
  V8_WARN_UNUSED_RESULT EmitResult Emit(RegExpCompiler* compiler,
                                        Trace* trace) override;
  void GetQuickCheckDetails(QuickCheckDetails* details,
                            RegExpCompiler* compiler,
                            int characters_filled_in,
                            bool not_at_start,
                            int budget) override {
    return;
  }
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override;

 private:
  int start_reg_;
  int end_reg_;
  bool read_backward_;
};

class EndNode : public RegExpNode {
 public:
  enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
  EndNode(Action action, Zone* zone) : RegExpNode(zone), action_(action) {
    EatsAtLeastInfo large(kLargeEatsAtLeastValue);
    if (action == BACKTRACK) set_eats_at_least_info(large);
  }
  EndNode* AsEndNode() override { return this; }
  void Accept(NodeVisitor* visitor) override;
  V8_WARN_UNUSED_RESULT EmitResult Emit(RegExpCompiler* compiler,
                                        Trace* trace) override;
  void GetQuickCheckDetails(QuickCheckDetails* details,
                            RegExpCompiler* compiler,
                            int characters_filled_in,
                            bool not_at_start,
                            int budget) override;
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override {}
  Action action() const { return action_; }

  virtual bool IsBacktrack() const override { return action_ == BACKTRACK; }

 private:
  Action action_;
};

class NegativeSubmatchSuccess : public EndNode {
 public:
  NegativeSubmatchSuccess(int stack_pointer_reg,
                          int position_reg,
                          int clear_capture_count,
                          int 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) {}
  V8_WARN_UNUSED_RESULT EmitResult Emit(RegExpCompiler* compiler,
                                        Trace* trace) override;
  NegativeSubmatchSuccess* AsNegativeSubmatchSuccess() override { return this; }

 private:
  int stack_pointer_register_;
  int current_position_register_;
  int clear_capture_count_;
  int clear_capture_start_;

  friend class RegExpNodePrinter<RegExpNode>;
};

class Guard : public ZoneObject {
 public:
  enum Relation { LT, GEQ };
  Guard(int reg, Relation op, int value) : reg_(reg), op_(op), value_(value) {}
  int reg() const { return reg_; }
  Relation op() const { return op_; }
  int value() const { return value_; }

 private:
  int reg_;
  Relation op_;
  int value_;
};

class GuardedAlternative {
 public:
  explicit GuardedAlternative(RegExpNode* node)
      : node_(node), guards_(nullptr) {}
  void AddGuard(Guard* guard, Zone* zone);
  RegExpNode* node() const { return node_; }
  void set_node(RegExpNode* node) { node_ = node; }
  const ZoneList<Guard*>* guards() const { return guards_; }

 private:
  RegExpNode* node_;
  // TODO(pthier): There are currently no uses of multiple guards. Consider
  // removing the ZoneList.
  ZoneList<Guard*>* guards_;
};

class AlternativeGeneration;

class ChoiceNode : public RegExpNode {
 public:
  explicit ChoiceNode(int expected_size, Zone* zone)
      : RegExpNode(zone),
        alternatives_(
            zone->New<ZoneList<GuardedAlternative>>(expected_size, zone)),
        not_at_start_(false),
        being_calculated_(false) {}
  ChoiceNode* AsChoiceNode() override { return this; }
  void Accept(NodeVisitor* visitor) override;
  void AddAlternative(GuardedAlternative node) {
    alternatives()->Add(node, zone());
  }
  ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
  V8_WARN_UNUSED_RESULT EmitResult Emit(RegExpCompiler* compiler,
                                        Trace* trace) override;
  void GetQuickCheckDetails(QuickCheckDetails* details,
                            RegExpCompiler* compiler,
                            int characters_filled_in,
                            bool not_at_start,
                            int budget) override;
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override;

  bool being_calculated() const { return being_calculated_; }
  bool not_at_start() const { return not_at_start_; }
  void set_not_at_start() { not_at_start_ = true; }
  void set_being_calculated(bool b) { being_calculated_ = b; }
  virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
    return true;
  }
  virtual bool read_backward() const { return false; }

 protected:
  int FixedLengthLoopLengthForAlternative(GuardedAlternative* alternative);
  ZoneList<GuardedAlternative>* alternatives_;

 private:
  template <typename...>
  friend class Analysis;

  void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                     Guard* guard,
                     Trace* trace);
  int CalculatePreloadCharacters(RegExpCompiler* compiler, int eats_at_least);
  V8_WARN_UNUSED_RESULT EmitResult
  EmitOutOfLineContinuation(RegExpCompiler* compiler,
                            Trace* trace,
                            GuardedAlternative alternative,
                            AlternativeGeneration* alt_gen,
                            int preload_characters,
                            bool next_expects_preload);
  void SetUpPreLoad(RegExpCompiler* compiler,
                    Trace* current_trace,
                    PreloadState* preloads);
  void AssertGuardsMentionRegisters(Trace* trace);
  int EmitOptimizedUnanchoredSearch(RegExpCompiler* compiler,
                                    Trace* trace,
                                    SpecialLoopState* search_loop_state);
  // Returns nullptr on failure.
  // TODO(jgruber): Consider wrapping the return value in EmitResult.
  V8_WARN_UNUSED_RESULT Trace* EmitFixedLengthLoop(
      RegExpCompiler* compiler,
      Trace* trace,
      AlternativeGenerationList* alt_gens,
      PreloadState* preloads,
      SpecialLoopState* fixed_length_loop_state,
      int text_length,
      RegExpFlags flags);
  V8_WARN_UNUSED_RESULT EmitResult
  EmitChoices(RegExpCompiler* compiler,
              AlternativeGenerationList* alt_gens,
              int first_choice,
              Trace* trace,
              PreloadState* preloads,
              RegExpFlags flags);

  // 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 NegativeLookaroundChoiceNode : public ChoiceNode {
 public:
  explicit NegativeLookaroundChoiceNode(GuardedAlternative this_must_fail,
                                        GuardedAlternative then_do_this,
                                        Zone* zone)
      : ChoiceNode(2, zone) {
    AddAlternative(this_must_fail);
    AddAlternative(then_do_this);
  }
  void GetQuickCheckDetails(QuickCheckDetails* details,
                            RegExpCompiler* compiler,
                            int characters_filled_in,
                            bool not_at_start,
                            int budget) override;
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override {
    continue_node()->FillInBMInfo(isolate, offset, budget - 1, bm,
                                  not_at_start);
    if (offset == 0) set_bm_info(not_at_start, bm);
  }
  static constexpr int kLookaroundIndex = 0;
  static constexpr int kContinueIndex = 1;
  RegExpNode* lookaround_node() {
    return alternatives()->at(kLookaroundIndex).node();
  }
  RegExpNode* continue_node() {
    return alternatives()->at(kContinueIndex).node();
  }
  // For a negative lookahead we don't emit the quick check for the
  // 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.
  bool try_to_emit_quick_check_for_alternative(bool is_first) override {
    return !is_first;
  }
  NegativeLookaroundChoiceNode* AsNegativeLookaroundChoiceNode() override {
    return this;
  }
  void Accept(NodeVisitor* visitor) override;
};

class LoopChoiceNode : public ChoiceNode {
 public:
  LoopChoiceNode(bool body_can_be_zero_length, bool read_backward, Zone* zone)
      : ChoiceNode(2, zone),
        loop_node_(nullptr),
        continue_node_(nullptr),
        body_can_be_zero_length_(body_can_be_zero_length),
        read_backward_(read_backward) {}
  void AddLoopAlternative(GuardedAlternative alt);
  void AddContinueAlternative(GuardedAlternative alt);
  V8_WARN_UNUSED_RESULT EmitResult Emit(RegExpCompiler* compiler,
                                        Trace* trace) override;
  void GetQuickCheckDetails(QuickCheckDetails* details,
                            RegExpCompiler* compiler,
                            int characters_filled_in,
                            bool not_at_start,
                            int budget) override;
  void FillInBMInfo(Isolate* isolate,
                    int offset,
                    int budget,
                    BoyerMooreLookahead* bm,
                    bool not_at_start) override;
  RegExpNode* loop_node() const { return loop_node_; }
  RegExpNode* continue_node() const { return continue_node_; }
  bool body_can_be_zero_length() const { return body_can_be_zero_length_; }
  bool read_backward() const override { return read_backward_; }
  LoopChoiceNode* AsLoopChoiceNode() override { return this; }
  void Accept(NodeVisitor* visitor) override;

 private:
  // AddAlternative is made private for loop nodes because alternatives
  // should not be added freely, we need to keep track of which node
  // 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_;
  bool read_backward_;
};

class NodeVisitor {
 public:
  virtual ~NodeVisitor() = default;
#define DECLARE_VISIT(Type) virtual void Visit##Type(Type##Node* that) = 0;
  FOR_EACH_NODE_TYPE(DECLARE_VISIT)
#undef DECLARE_VISIT
};

}  // namespace dart

#endif  // V8_REGEXP_REGEXP_NODES_H_