path: root/js/src/irregexp/RegExpEngine.h

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

// Copyright 2012 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef V8_JSREGEXP_H_
#define V8_JSREGEXP_H_

#include "jscntxt.h"

#include "ds/SplayTree.h"
#include "jit/Label.h"
#include "vm/RegExpObject.h"

namespace js {

class MatchPairs;
class RegExpShared;

namespace jit {
    class Label;
    class JitCode;
}

namespace irregexp {

class RegExpTree;
class RegExpMacroAssembler;

struct RegExpCompileData
{
    RegExpCompileData()
      : tree(nullptr),
        simple(true),
        contains_anchor(false),
        capture_count(0)
    {}

    RegExpTree* tree;
    bool simple;
    bool contains_anchor;
    int capture_count;
};

struct RegExpCode
{
    jit::JitCode* jitCode;
    uint8_t* byteCode;

    RegExpCode()
      : jitCode(nullptr), byteCode(nullptr)
    {}

    bool empty() {
        return !jitCode && !byteCode;
    }

    void destroy() {
        js_free(byteCode);
    }
};

RegExpCode
CompilePattern(JSContext* cx, RegExpShared* shared, RegExpCompileData* data,
               HandleLinearString sample,  bool is_global, bool ignore_case,
               bool is_ascii, bool match_only, bool force_bytecode, bool sticky,
               bool unicode);

// Note: this may return RegExpRunStatus_Error if an interrupt was requested
// while the code was executing.
template <typename CharT>
RegExpRunStatus
ExecuteCode(JSContext* cx, jit::JitCode* codeBlock, const CharT* chars, size_t start,
            size_t length, MatchPairs* matches, size_t* endIndex);

template <typename CharT>
RegExpRunStatus
InterpretCode(JSContext* cx, const uint8_t* byteCode, const CharT* chars, size_t start,
              size_t length, MatchPairs* matches, size_t* endIndex);

#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(Lookaround)                                                  \
  VISIT(BackReference)                                               \
  VISIT(Empty)                                                       \
  VISIT(Text)

#define FORWARD_DECLARE(Name) class RegExp##Name;
FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE)
#undef FORWARD_DECLARE

// InfallibleVector is like Vector, but all its methods are infallible (they
// crash on OOM). We use this class instead of Vector to avoid a ton of
// MOZ_MUST_USE warnings in irregexp code (imported from V8).
template<typename T, size_t N>
class InfallibleVector
{
    Vector<T, N, LifoAllocPolicy<Infallible>> vector_;

    InfallibleVector(const InfallibleVector&) = delete;
    void operator=(const InfallibleVector&) = delete;

  public:
    explicit InfallibleVector(const LifoAllocPolicy<Infallible>& alloc) : vector_(alloc) {}

    void append(const T& t) { MOZ_ALWAYS_TRUE(vector_.append(t)); }
    void append(const T* begin, size_t length) { MOZ_ALWAYS_TRUE(vector_.append(begin, length)); }

    void clear() { vector_.clear(); }
    void popBack() { vector_.popBack(); }
    void reserve(size_t n) { MOZ_ALWAYS_TRUE(vector_.reserve(n)); }

    size_t length() const { return vector_.length(); }
    T popCopy() { return vector_.popCopy(); }

    T* begin() { return vector_.begin(); }
    const T* begin() const { return vector_.begin(); }

    T& operator[](size_t index) { return vector_[index]; }
    const T& operator[](size_t index) const { return vector_[index]; }

    InfallibleVector& operator=(InfallibleVector&& rhs) { vector_ = Move(rhs.vector_); return *this; }
};

class CharacterRange;
typedef InfallibleVector<CharacterRange, 1> CharacterRangeVector;

// Represents code units in the range from from_ to to_, both ends are
// inclusive.
class CharacterRange
{
  public:
    CharacterRange()
      : from_(0), to_(0)
    {}

    CharacterRange(char16_t from, char16_t to)
      : from_(from), to_(to)
    {}

    static void AddClassEscape(LifoAlloc* alloc, char16_t type, CharacterRangeVector* ranges);
    static void AddClassEscapeUnicode(LifoAlloc* alloc, char16_t type,
                                      CharacterRangeVector* ranges, bool ignoreCase);

    static inline CharacterRange Singleton(char16_t value) {
        return CharacterRange(value, value);
    }
    static inline CharacterRange Range(char16_t from, char16_t to) {
        MOZ_ASSERT(from <= to);
        return CharacterRange(from, to);
    }
    static inline CharacterRange Everything() {
        return CharacterRange(0, 0xFFFF);
    }
    bool Contains(char16_t i) { return from_ <= i && i <= to_; }
    char16_t from() const { return from_; }
    void set_from(char16_t value) { from_ = value; }
    char16_t to() const { return to_; }
    void set_to(char16_t value) { to_ = value; }
    bool is_valid() { return from_ <= to_; }
    bool IsEverything(char16_t max) { return from_ == 0 && to_ >= max; }
    bool IsSingleton() { return (from_ == to_); }
    void AddCaseEquivalents(bool is_ascii, bool unicode, CharacterRangeVector* ranges);

    static void Split(const LifoAlloc* alloc,
                      CharacterRangeVector base,
                      const Vector<int>& overlay,
                      CharacterRangeVector* included,
                      CharacterRangeVector* excluded);

    // Whether a range list is in canonical form: Ranges ordered by from value,
    // and ranges non-overlapping and non-adjacent.
    static bool IsCanonical(const CharacterRangeVector& ranges);

    // Convert range list to canonical form. The characters covered by the ranges
    // will still be the same, but no character is in more than one range, and
    // adjacent ranges are merged. The resulting list may be shorter than the
    // original, but cannot be longer.
    static void Canonicalize(CharacterRangeVector& ranges);

    // Negate the contents of a character range in canonical form.
    static void Negate(const LifoAlloc* alloc,
                       CharacterRangeVector src,
                       CharacterRangeVector* dst);

    static const int kStartMarker = (1 << 24);
    static const int kPayloadMask = (1 << 24) - 1;

  private:
    char16_t from_;
    char16_t to_;
};

// A set of unsigned integers that behaves especially well on small
// integers (< 32).
class OutSet
{
  public:
    OutSet()
      : first_(0), remaining_(nullptr), successors_(nullptr)
    {}

    OutSet* Extend(LifoAlloc* alloc, unsigned value);
    bool Get(unsigned value);
    static const unsigned kFirstLimit = 32;

  private:
    typedef InfallibleVector<OutSet*, 1> OutSetVector;
    typedef InfallibleVector<unsigned, 1> RemainingVector;

    // 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(LifoAlloc* alloc, unsigned value);

    // 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.
    OutSetVector* successors() { return successors_; }

    OutSet(uint32_t first, RemainingVector* remaining)
      : first_(first), remaining_(remaining), successors_(nullptr)
    {}

    RemainingVector& remaining() { return *remaining_; }

    uint32_t first_;
    RemainingVector* remaining_;
    OutSetVector* 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:
    explicit DispatchTable(LifoAlloc* alloc)
    {}

    class Entry {
      public:
        Entry()
          : from_(0), to_(0), out_set_(nullptr)
        {}

        Entry(char16_t from, char16_t to, OutSet* out_set)
          : from_(from), to_(to), out_set_(out_set)
        {}

        char16_t from() { return from_; }
        char16_t to() { return to_; }
        void set_to(char16_t value) { to_ = value; }
        void AddValue(LifoAlloc* alloc, int value) {
            out_set_ = out_set_->Extend(alloc, value);
        }
        OutSet* out_set() { return out_set_; }
      private:
        char16_t from_;
        char16_t to_;
        OutSet* out_set_;
    };

    void AddRange(LifoAlloc* alloc, CharacterRange range, int value);
    OutSet* Get(char16_t value);
    void Dump();

  private:
    // There can't be a static empty set since it allocates its
    // successors in a LifoAlloc and caches them.
    OutSet* empty() { return &empty_; }
    OutSet empty_;
};

class TextElement
{
  public:
    enum TextType {
        ATOM,
        CHAR_CLASS
    };

    static TextElement Atom(RegExpAtom* atom);
    static TextElement CharClass(RegExpCharacterClass* char_class);

    int cp_offset() const { return cp_offset_; }
    void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; }
    int length() const;

    TextType text_type() const { return text_type_; }

    RegExpTree* tree() const { return tree_; }

    RegExpAtom* atom() const {
        MOZ_ASSERT(text_type() == ATOM);
        return reinterpret_cast<RegExpAtom*>(tree());
    }

    RegExpCharacterClass* char_class() const {
        MOZ_ASSERT(text_type() == CHAR_CLASS);
        return reinterpret_cast<RegExpCharacterClass*>(tree());
    }

  private:
    TextElement(TextType text_type, RegExpTree* tree)
      : cp_offset_(-1), text_type_(text_type), tree_(tree)
    {}

    int cp_offset_;
    TextType text_type_;
    RegExpTree* tree_;
};

typedef InfallibleVector<TextElement, 1> TextElementVector;

class NodeVisitor;
class RegExpCompiler;
class Trace;
class BoyerMooreLookahead;

struct NodeInfo
{
    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;
};

// 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(int characters)
      : characters_(characters),
        mask_(0),
        value_(0),
        cannot_match_(false)
    {}

    bool Rationalize(bool ascii);

    // Merge in the information from another branch of an alternation.
    void Merge(QuickCheckDetails* other, int from_index);

    // Advance the current position by some amount.
    void Advance(int by, bool ascii);

    void Clear();

    bool cannot_match() { return cannot_match_; }
    void set_cannot_match() { cannot_match_ = true; }

    int characters() { return characters_; }
    void set_characters(int characters) { characters_ = characters; }

    struct Position {
        Position() : mask(0), value(0), determines_perfectly(false) { }
        char16_t mask;
        char16_t value;
        bool determines_perfectly;
    };

    Position* positions(int index) {
        MOZ_ASSERT(index >= 0);
        MOZ_ASSERT(index < characters_);
        return positions_ + index;
    }

    uint32_t mask() { return mask_; }
    uint32_t value() { return value_; }

  private:
    // How many characters do we have quick check information from.  This is
    // the same for all branches of a choice node.
    int characters_;
    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_;
};

class RegExpNode
{
  public:
    explicit RegExpNode(LifoAlloc* alloc);
    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;

    // How many characters must this node consume at a minimum in order to
    // succeed.  If we have found at least 'still_to_find' characters that
    // must be consumed there is no need to ask any following nodes whether
    // they are sure to eat any more characters.  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.
    virtual int EatsAtLeast(int still_to_find, int 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,
                        jit::Label* 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,
                                      int characters_filled_in,
                                      bool not_at_start) = 0;

    static const int kNodeIsTooComplexForGreedyLoops = -1;

    virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }

    // 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;
    }

    static const int kRecursionBudget = 200;

    // 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.
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start) {
        MOZ_CRASH("Bad call");
    }

    // If we know that the input is ASCII then there are some nodes that can
    // never match.  This method returns a node that can be substituted for
    // itself, or nullptr if the node can never match.
    virtual RegExpNode* FilterASCII(int depth, bool ignore_case, bool unicode) { return this; }

    // Helper for FilterASCII.
    RegExpNode* replacement() {
        MOZ_ASSERT(info()->replacement_calculated);
        return replacement_;
    }
    RegExpNode* set_replacement(RegExpNode* replacement) {
        info()->replacement_calculated = true;
        replacement_ =  replacement;
        return replacement;  // For convenience.
    }

    // 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);
    }

    jit::Label* 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;

    NodeInfo* info() { return &info_; }

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

    LifoAlloc* alloc() const { return alloc_; }

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

    LifoAlloc* alloc_;
};

// A simple closed interval.
class Interval
{
  public:
    Interval() : from_(kNone), to_(kNone) { }

    Interval(int from, int to) : from_(from), to_(to) { }

    Interval Union(Interval that) {
        if (that.from_ == kNone)
            return *this;
        else if (from_ == kNone)
            return that;
        else
            return Interval(Min(from_, that.from_), Max(to_, that.to_));
    }

    bool Contains(int value) {
        return (from_ <= value) && (value <= to_);
    }

    bool is_empty() { return from_ == kNone; }

    int from() const { return from_; }
    int to() const { return to_; }

    static Interval Empty() { return Interval(); }
    static const int kNone = -1;

  private:
    int from_;
    int to_;
};

class SeqRegExpNode : public RegExpNode
{
  public:
    explicit SeqRegExpNode(RegExpNode* on_success)
      : RegExpNode(on_success->alloc()), on_success_(on_success)
    {}

    RegExpNode* on_success() { return on_success_; }
    void set_on_success(RegExpNode* node) { on_success_ = node; }
    virtual RegExpNode* FilterASCII(int depth, bool ignore_case, bool unicode);
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start);

  protected:
    RegExpNode* FilterSuccessor(int depth, bool ignore_case, bool unicode);

  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
    };

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

    static ActionNode* SetRegister(int reg, int val, RegExpNode* on_success);
    static ActionNode* IncrementRegister(int reg, RegExpNode* on_success);
    static ActionNode* StorePosition(int reg,
                                     bool is_capture,
                                     RegExpNode* on_success);
    static ActionNode* ClearCaptures(Interval range, RegExpNode* on_success);
    static ActionNode* BeginSubmatch(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);
    virtual void Accept(NodeVisitor* visitor);
    virtual void Emit(RegExpCompiler* compiler, Trace* trace);
    virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
    virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                      RegExpCompiler* compiler,
                                      int filled_in,
                                      bool not_at_start) {
        return on_success()->GetQuickCheckDetails(
                                                  details, compiler, filled_in, not_at_start);
    }
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start);
    ActionType action_type() { return action_type_; }
    // TODO(erikcorry): We should allow some action nodes in greedy loops.
    virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }

  private:
    union {
        struct {
            int reg;
            int value;
        } u_store_register;
        struct {
            int reg;
        } u_increment_register;
        struct {
            int reg;
            bool is_capture;
        } u_position_register;
        struct {
            int stack_pointer_register;
            int current_position_register;
            int clear_register_count;
            int clear_register_from;
        } u_submatch;
        struct {
            int start_register;
            int repetition_register;
            int repetition_limit;
        } u_empty_match_check;
        struct {
            int range_from;
            int range_to;
        } u_clear_captures;
    } data_;
    ActionType action_type_;
    friend class DotPrinter;
};

class TextNode : public SeqRegExpNode
{
  public:
    TextNode(TextElementVector* elements,
             bool read_backward,
             RegExpNode* on_success)
      : SeqRegExpNode(on_success),
        elements_(elements),
        read_backward_(read_backward)
    {}

    TextNode(RegExpCharacterClass* that,
             bool read_backward,
             RegExpNode* on_success)
      : SeqRegExpNode(on_success),
        elements_(alloc()->newInfallible<TextElementVector>(*alloc())),
        read_backward_(read_backward)
    {
        elements_->append(TextElement::CharClass(that));
    }

    virtual void Accept(NodeVisitor* visitor);
    virtual void Emit(RegExpCompiler* compiler, Trace* trace);
    virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
    virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                      RegExpCompiler* compiler,
                                      int characters_filled_in,
                                      bool not_at_start);
    TextElementVector& elements() { return *elements_; }
    bool read_backward() { return read_backward_; }
    void MakeCaseIndependent(bool is_ascii, bool unicode);
    virtual int GreedyLoopTextLength();
    virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
                                                         RegExpCompiler* compiler);
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start);
    void CalculateOffsets();
    virtual RegExpNode* FilterASCII(int depth, bool ignore_case, bool unicode);

  private:
    enum TextEmitPassType {
        NON_ASCII_MATCH,             // Check for characters that can't 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.
    };
    static bool SkipPass(int pass, bool ignore_case);
    static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH;
    static const int kLastPass = CHARACTER_CLASS_MATCH;
    void TextEmitPass(RegExpCompiler* compiler,
                      TextEmitPassType pass,
                      bool preloaded,
                      Trace* trace,
                      bool first_element_checked,
                      int* checked_up_to);
    int Length();
    TextElementVector* elements_;
    bool read_backward_;
};

class AssertionNode : public SeqRegExpNode
{
  public:
    enum AssertionType {
        AT_END,
        AT_START,
        AT_BOUNDARY,
        AT_NON_BOUNDARY,
        AFTER_NEWLINE,
        NOT_AFTER_LEAD_SURROGATE,
        NOT_IN_SURROGATE_PAIR
    };
    AssertionNode(AssertionType t, RegExpNode* on_success)
      : SeqRegExpNode(on_success), assertion_type_(t)
    {}

    static AssertionNode* AtEnd(RegExpNode* on_success) {
        return on_success->alloc()->newInfallible<AssertionNode>(AT_END, on_success);
    }
    static AssertionNode* AtStart(RegExpNode* on_success) {
        return on_success->alloc()->newInfallible<AssertionNode>(AT_START, on_success);
    }
    static AssertionNode* AtBoundary(RegExpNode* on_success) {
        return on_success->alloc()->newInfallible<AssertionNode>(AT_BOUNDARY, on_success);
    }
    static AssertionNode* AtNonBoundary(RegExpNode* on_success) {
        return on_success->alloc()->newInfallible<AssertionNode>(AT_NON_BOUNDARY, on_success);
    }
    static AssertionNode* AfterNewline(RegExpNode* on_success) {
        return on_success->alloc()->newInfallible<AssertionNode>(AFTER_NEWLINE, on_success);
    }
    static AssertionNode* NotAfterLeadSurrogate(RegExpNode* on_success) {
        return on_success->alloc()->newInfallible<AssertionNode>(NOT_AFTER_LEAD_SURROGATE,
                                                                 on_success);
    }
    static AssertionNode* NotInSurrogatePair(RegExpNode* on_success) {
        return on_success->alloc()->newInfallible<AssertionNode>(NOT_IN_SURROGATE_PAIR,
                                                                 on_success);
    }
    virtual void Accept(NodeVisitor* visitor);
    virtual void Emit(RegExpCompiler* compiler, Trace* trace);
    virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
    virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                      RegExpCompiler* compiler,
                                      int filled_in,
                                      bool not_at_start);
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start);
    AssertionType assertion_type() { return assertion_type_; }

  private:
    void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace);
    enum IfPrevious { kIsNonWord, kIsWord };
    void BacktrackIfPrevious(RegExpCompiler* compiler,
                             Trace* trace,
                             IfPrevious backtrack_if_previous);
    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)
    {}

    virtual void Accept(NodeVisitor* visitor);
    int start_register() { return start_reg_; }
    int end_register() { return end_reg_; }
    bool read_backward() { return read_backward_; }
    virtual void Emit(RegExpCompiler* compiler, Trace* trace);
    virtual int EatsAtLeast(int still_to_find,
                            int recursion_depth,
                            bool not_at_start);
    virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                      RegExpCompiler* compiler,
                                      int characters_filled_in,
                                      bool not_at_start) {
        return;
    }
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start);

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

class EndNode : public RegExpNode
{
  public:
    enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };

    explicit EndNode(LifoAlloc* alloc, Action action)
      : RegExpNode(alloc), action_(action)
    {}

    virtual void Accept(NodeVisitor* visitor);
    virtual void Emit(RegExpCompiler* compiler, Trace* trace);
    virtual int EatsAtLeast(int still_to_find,
                            int recursion_depth,
                            bool not_at_start) { return 0; }
    virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                      RegExpCompiler* compiler,
                                      int characters_filled_in,
                                      bool not_at_start)
    {
        // Returning 0 from EatsAtLeast should ensure we never get here.
        MOZ_CRASH("Bad call");
    }
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start) {
        // Returning 0 from EatsAtLeast should ensure we never get here.
        MOZ_CRASH("Bad call");
    }

  private:
    Action action_;
};

class NegativeSubmatchSuccess : public EndNode
{
  public:
    NegativeSubmatchSuccess(LifoAlloc* alloc,
                            int stack_pointer_reg,
                            int position_reg,
                            int clear_capture_count,
                            int clear_capture_start)
      : EndNode(alloc, NEGATIVE_SUBMATCH_SUCCESS),
        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:
    int stack_pointer_register_;
    int current_position_register_;
    int clear_capture_count_;
    int clear_capture_start_;
};

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

    int reg() { return reg_; }
    Relation op() { return op_; }
    int value() { return value_; }

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

typedef InfallibleVector<Guard*, 1> GuardVector;

class GuardedAlternative
{
  public:
    explicit GuardedAlternative(RegExpNode* node)
      : node_(node), guards_(nullptr)
    {}

    void AddGuard(LifoAlloc* alloc, Guard* guard);
    RegExpNode* node() const { return node_; }
    void set_node(RegExpNode* node) { node_ = node; }
    const GuardVector* guards() const { return guards_; }

  private:
    RegExpNode* node_;
    GuardVector* guards_;
};

typedef InfallibleVector<GuardedAlternative, 0> GuardedAlternativeVector;

class AlternativeGeneration;

class ChoiceNode : public RegExpNode
{
  public:
    explicit ChoiceNode(LifoAlloc* alloc, int expected_size)
      : RegExpNode(alloc),
        alternatives_(*alloc),
        table_(nullptr),
        not_at_start_(false),
        being_calculated_(false)
    {
        alternatives_.reserve(expected_size);
    }

    virtual void Accept(NodeVisitor* visitor);
    void AddAlternative(GuardedAlternative node) {
        alternatives_.append(node);
    }

    GuardedAlternativeVector& alternatives() { return alternatives_; }
    DispatchTable* GetTable(bool ignore_case);
    virtual void Emit(RegExpCompiler* compiler, Trace* trace);
    virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
    int EatsAtLeastHelper(int still_to_find,
                          int budget,
                          RegExpNode* ignore_this_node,
                          bool not_at_start);
    virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                      RegExpCompiler* compiler,
                                      int characters_filled_in,
                                      bool not_at_start);
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start);

    bool being_calculated() { return being_calculated_; }
    bool not_at_start() { 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(int i) { return true; }
    virtual RegExpNode* FilterASCII(int depth, bool ignore_case, bool unicode);
    virtual bool read_backward() { return false; }

  protected:
    int GreedyLoopTextLengthForAlternative(GuardedAlternative* alternative);
    GuardedAlternativeVector alternatives_;

  private:
    friend class Analysis;
    void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                       Guard* guard,
                       Trace* trace);
    int CalculatePreloadCharacters(RegExpCompiler* compiler, int eats_at_least);
    void EmitOutOfLineContinuation(RegExpCompiler* compiler,
                                   Trace* trace,
                                   GuardedAlternative alternative,
                                   AlternativeGeneration* alt_gen,
                                   int preload_characters,
                                   bool next_expects_preload);
    DispatchTable* table_;

    // 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(LifoAlloc* alloc,
                                         GuardedAlternative this_must_fail,
                                         GuardedAlternative then_do_this)
      : ChoiceNode(alloc, 2)
    {
        AddAlternative(this_must_fail);
        AddAlternative(then_do_this);
    }
    virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
    virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                      RegExpCompiler* compiler,
                                      int characters_filled_in,
                                      bool not_at_start);
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start);

    // 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.
    virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; }
    virtual RegExpNode* FilterASCII(int depth, bool ignore_case, bool unicode);
};

class LoopChoiceNode : public ChoiceNode
{
  public:
    explicit LoopChoiceNode(LifoAlloc* alloc, bool body_can_be_zero_length,
                            bool read_backward)
      : ChoiceNode(alloc, 2),
        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);
    virtual void Emit(RegExpCompiler* compiler, Trace* trace);
    virtual int EatsAtLeast(int still_to_find,  int budget, bool not_at_start);
    virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                      RegExpCompiler* compiler,
                                      int characters_filled_in,
                                      bool not_at_start);
    virtual bool FillInBMInfo(int offset,
                              int budget,
                              BoyerMooreLookahead* bm,
                              bool not_at_start);
    RegExpNode* loop_node() { return loop_node_; }
    RegExpNode* continue_node() { return continue_node_; }
    bool body_can_be_zero_length() { return body_can_be_zero_length_; }
    virtual bool read_backward() { return read_backward_; }
    virtual void Accept(NodeVisitor* visitor);
    virtual RegExpNode* FilterASCII(int depth, bool ignore_case, bool unicode);

  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_;
};

// 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,
         int ranges_size,
         Interval new_range);

class BoyerMoorePositionInfo
{
  public:
    explicit BoyerMoorePositionInfo(LifoAlloc* alloc, bool unicode_ignore_case)
      : map_(*alloc),
        map_count_(0),
        w_(kNotYet),
        s_(kNotYet),
        d_(kNotYet),
        surrogate_(kNotYet),
        unicode_ignore_case_(unicode_ignore_case)
    {
        map_.reserve(kMapSize);
        for (int i = 0; i < kMapSize; i++)
            map_.append(false);
    }

    bool& at(int i) { return map_[i]; }

    static const int kMapSize = 128;
    static const int kMask = kMapSize - 1;

    int map_count() const { return map_count_; }

    void Set(int character);
    void SetInterval(const Interval& interval);
    void SetAll();
    bool is_non_word() { return w_ == kLatticeOut; }
    bool is_word() { return w_ == kLatticeIn; }

  private:
    InfallibleVector<bool, 0> map_;
    int 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.

    // True if the RegExp has unicode and ignoreCase flags.
    bool unicode_ignore_case_;
};

typedef InfallibleVector<BoyerMoorePositionInfo*, 1> BoyerMoorePositionInfoVector;

class BoyerMooreLookahead
{
  public:
    BoyerMooreLookahead(LifoAlloc* alloc, size_t length, RegExpCompiler* compiler);

    int length() { return length_; }
    int max_char() { return max_char_; }
    RegExpCompiler* compiler() { return compiler_; }

    int Count(int map_number) {
        return bitmaps_[map_number]->map_count();
    }

    BoyerMoorePositionInfo* at(int i) { return bitmaps_[i]; }

    void Set(int map_number, int character) {
        if (character > max_char_) return;
        BoyerMoorePositionInfo* info = bitmaps_[map_number];
        info->Set(character);
    }

    void SetInterval(int map_number, const Interval& interval) {
        if (interval.from() > max_char_) return;
        BoyerMoorePositionInfo* info = bitmaps_[map_number];
        if (interval.to() > max_char_) {
            info->SetInterval(Interval(interval.from(), max_char_));
        } else {
            info->SetInterval(interval);
        }
    }

    void SetAll(int map_number) {
        bitmaps_[map_number]->SetAll();
    }

    void SetRest(int from_map) {
        for (int i = from_map; i < length_; i++) SetAll(i);
    }
    bool EmitSkipInstructions(RegExpMacroAssembler* masm);

    bool CheckOverRecursed();

  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.
    int length_;
    RegExpCompiler* compiler_;

    // 0x7f for ASCII, 0xffff for UTF-16.
    int max_char_;
    BoyerMoorePositionInfoVector bitmaps_;

    int GetSkipTable(int min_lookahead,
                     int max_lookahead,
                     uint8_t* boolean_skip_table);
    bool FindWorthwhileInterval(int* from, int* to);
    int FindBestInterval(int max_number_of_chars, int 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
// where baz has been matched.
class Trace
{
  public:
    // A value for a property that is either known to be true, know to be false,
    // or not known.
    enum TriBool {
        UNKNOWN = -1, FALSE_VALUE = 0, TRUE_VALUE = 1
    };

    class DeferredAction {
      public:
        DeferredAction(ActionNode::ActionType action_type, int reg)
          : action_type_(action_type), reg_(reg), next_(nullptr)
        {}

        DeferredAction* next() { return next_; }
        bool Mentions(int reg);
        int reg() { return reg_; }
        ActionNode::ActionType action_type() { return action_type_; }
      private:
        ActionNode::ActionType action_type_;
        int reg_;
        DeferredAction* next_;
        friend class Trace;
    };

    class DeferredCapture : public DeferredAction {
      public:
        DeferredCapture(int reg, bool is_capture, Trace* trace)
          : DeferredAction(ActionNode::STORE_POSITION, reg),
            cp_offset_(trace->cp_offset()),
            is_capture_(is_capture)
        {}

        int cp_offset() { return cp_offset_; }
        bool is_capture() { return is_capture_; }
      private:
        int cp_offset_;
        bool is_capture_;
        void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; }
    };

    class DeferredSetRegister : public DeferredAction {
      public:
        DeferredSetRegister(int reg, int value)
          : DeferredAction(ActionNode::SET_REGISTER, reg),
            value_(value)
        {}
        int value() { return value_; }
      private:
        int value_;
    };

    class DeferredClearCaptures : public DeferredAction {
      public:
        explicit DeferredClearCaptures(Interval range)
          : DeferredAction(ActionNode::CLEAR_CAPTURES, -1),
            range_(range)
        {}

        Interval range() { return range_; }
      private:
        Interval range_;
    };

    class DeferredIncrementRegister : public DeferredAction {
      public:
        explicit DeferredIncrementRegister(int reg)
          : DeferredAction(ActionNode::INCREMENT_REGISTER, reg)
        {}
    };

    Trace()
      : cp_offset_(0),
        actions_(nullptr),
        backtrack_(nullptr),
        stop_node_(nullptr),
        loop_label_(nullptr),
        characters_preloaded_(0),
        bound_checked_up_to_(0),
        flush_budget_(100),
        at_start_(UNKNOWN)
    {}

    // End the trace.  This involves flushing the deferred actions in the trace
    // and pushing a backtrack location onto the backtrack stack.  Once this is
    // done we can start a new trace or go to one that has already been
    // generated.
    void Flush(RegExpCompiler* compiler, RegExpNode* successor);

    int cp_offset() { return cp_offset_; }
    DeferredAction* actions() { return actions_; }

    // A trivial trace is one that has no deferred actions or other state that
    // affects the assumptions used when generating code.  There is no recorded
    // backtrack location in a trivial trace, so with a trivial trace we will
    // generate code that, on a failure to match, gets the backtrack location
    // from the backtrack stack rather than using a direct jump instruction.  We
    // always start code generation with a trivial trace and non-trivial traces
    // are created as we emit code for nodes or add to the list of deferred
    // actions in the trace.  The location of the code generated for a node using
    // a trivial trace is recorded in a label in the node so that gotos can be
    // generated to that code.
    bool is_trivial() {
        return backtrack_ == nullptr &&
            actions_ == nullptr &&
            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(TriBool at_start) {
        at_start_ = at_start;
    }
    jit::Label* backtrack() { return backtrack_; }
    jit::Label* loop_label() { return loop_label_; }
    RegExpNode* stop_node() { return stop_node_; }
    int characters_preloaded() { return characters_preloaded_; }
    int bound_checked_up_to() { return bound_checked_up_to_; }
    int flush_budget() { return flush_budget_; }
    QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
    bool mentions_reg(int 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(int reg, int* 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) {
        MOZ_ASSERT(new_action->next_ == nullptr);
        new_action->next_ = actions_;
        actions_ = new_action;
    }

    void set_backtrack(jit::Label* backtrack) { backtrack_ = backtrack; }
    void set_stop_node(RegExpNode* node) { stop_node_ = node; }
    void set_loop_label(jit::Label* label) { loop_label_ = label; }
    void set_characters_preloaded(int count) { characters_preloaded_ = count; }
    void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; }
    void set_flush_budget(int to) { flush_budget_ = to; }
    void set_quick_check_performed(QuickCheckDetails* d) {
        quick_check_performed_ = *d;
    }
    void InvalidateCurrentCharacter();
    void AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler);

  private:
    int FindAffectedRegisters(LifoAlloc* alloc, OutSet* affected_registers);
    void PerformDeferredActions(LifoAlloc* alloc,
                                RegExpMacroAssembler* macro,
                                int max_register,
                                OutSet& affected_registers,
                                OutSet* registers_to_pop,
                                OutSet* registers_to_clear);
    void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
                                  int max_register,
                                  OutSet& registers_to_pop,
                                  OutSet& registers_to_clear);
    int cp_offset_;
    DeferredAction* actions_;
    jit::Label* backtrack_;
    RegExpNode* stop_node_;
    jit::Label* loop_label_;
    int characters_preloaded_;
    int bound_checked_up_to_;
    QuickCheckDetails quick_check_performed_;
    int flush_budget_;
    TriBool at_start_;
};

class NodeVisitor
{
  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:
//
//   +-------+        +------------+
//   |   .   |        |      .     |
//   +-------+  --->  +------------+
//   | word? |        | check word |
//   +-------+        +------------+
class Analysis : public NodeVisitor
{
  public:
    Analysis(JSContext* cx, bool ignore_case, bool is_ascii, bool unicode)
      : cx(cx),
        ignore_case_(ignore_case),
        is_ascii_(is_ascii),
        unicode_(unicode),
        error_message_(nullptr)
    {}

    void EnsureAnalyzed(RegExpNode* node);

#define DECLARE_VISIT(Type)                     \
    virtual void Visit##Type(Type##Node* that);
    FOR_EACH_NODE_TYPE(DECLARE_VISIT)
#undef DECLARE_VISIT
    virtual void VisitLoopChoice(LoopChoiceNode* that);

    bool has_failed() { return error_message_ != nullptr; }
    const char* errorMessage() {
        MOZ_ASSERT(error_message_ != nullptr);
        return error_message_;
    }
    void failASCII(const char* error_message) {
        error_message_ = error_message;
    }

  private:
    JSContext* cx;
    bool ignore_case_;
    bool is_ascii_;
    bool unicode_;
    const char* error_message_;

    Analysis(Analysis&) = delete;
    void operator=(Analysis&) = delete;
};

} }  // namespace js::irregexp

#endif  // V8_JSREGEXP_H_