// Copyright 2006-2008 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_

namespace v8 { namespace internal {


class RegExpMacroAssembler;


class RegExpImpl {
 public:
  // Creates a regular expression literal in the old space.
  // This function calls the garbage collector if necessary.
  static Handle<Object> CreateRegExpLiteral(Handle<JSFunction> constructor,
                                            Handle<String> pattern,
                                            Handle<String> flags,
                                            bool* has_pending_exception);

  // Returns a string representation of a regular expression.
  // Implements RegExp.prototype.toString, see ECMA-262 section 15.10.6.4.
  // This function calls the garbage collector if necessary.
  static Handle<String> ToString(Handle<Object> value);

  // Parses the RegExp pattern and prepares the JSRegExp object with
  // generic data and choice of implementation - as well as what
  // the implementation wants to store in the data field.
  static Handle<Object> Compile(Handle<JSRegExp> re,
                                Handle<String> pattern,
                                Handle<String> flags);

  // Implements RegExp.prototype.exec(string) function.
  // See ECMA-262 section 15.10.6.2.
  // This function calls the garbage collector if necessary.
  static Handle<Object> Exec(Handle<JSRegExp> regexp,
                             Handle<String> subject,
                             Handle<Object> index);

  // Call RegExp.prototyp.exec(string) in a loop.
  // Used by String.prototype.match and String.prototype.replace.
  // This function calls the garbage collector if necessary.
  static Handle<Object> ExecGlobal(Handle<JSRegExp> regexp,
                                   Handle<String> subject);

  // Stores an uncompiled RegExp pattern in the JSRegExp object.
  // It will be compiled by JSCRE when first executed.
  static Handle<Object> JscrePrepare(Handle<JSRegExp> re,
                                     Handle<String> pattern,
                                     JSRegExp::Flags flags);

  // Prepares a JSRegExp object with Irregexp-specific data.
  static Handle<Object> IrregexpPrepare(Handle<JSRegExp> re,
                                        Handle<String> pattern,
                                        JSRegExp::Flags flags);


  // Compile the pattern using JSCRE and store the result in the
  // JSRegExp object.
  static Handle<Object> JscreCompile(Handle<JSRegExp> re);

  static Handle<Object> AtomCompile(Handle<JSRegExp> re,
                                    Handle<String> pattern,
                                    JSRegExp::Flags flags,
                                    Handle<String> match_pattern);
  static Handle<Object> AtomExec(Handle<JSRegExp> regexp,
                                 Handle<String> subject,
                                 Handle<Object> index);

  static Handle<Object> AtomExecGlobal(Handle<JSRegExp> regexp,
                                       Handle<String> subject);

  static Handle<Object> JscreCompile(Handle<JSRegExp> re,
                                     Handle<String> pattern,
                                     JSRegExp::Flags flags);

  // Execute a compiled JSCRE pattern.
  static Handle<Object> JscreExec(Handle<JSRegExp> regexp,
                                  Handle<String> subject,
                                  Handle<Object> index);

  // Execute an Irregexp bytecode pattern.
  static Handle<Object> IrregexpExec(Handle<JSRegExp> regexp,
                                     Handle<String> subject,
                                     Handle<Object> index);

  static Handle<Object> JscreExecGlobal(Handle<JSRegExp> regexp,
                                        Handle<String> subject);

  static Handle<Object> IrregexpExecGlobal(Handle<JSRegExp> regexp,
                                           Handle<String> subject);

  static void NewSpaceCollectionPrologue();
  static void OldSpaceCollectionPrologue();

  // Converts a source string to a 16 bit flat string.  The string
  // will be either sequential or it will be a SlicedString backed
  // by a flat string.
  static Handle<String> StringToTwoByte(Handle<String> pattern);
  static Handle<String> CachedStringToTwoByte(Handle<String> pattern);

  static const int kIrregexpImplementationIndex = 0;
  static const int kIrregexpNumberOfCapturesIndex = 1;
  static const int kIrregexpNumberOfRegistersIndex = 2;
  static const int kIrregexpCodeIndex = 3;
  static const int kIrregexpDataLength = 4;

  static const int kJscreNumberOfCapturesIndex = 0;
  static const int kJscreInternalIndex = 1;
  static const int kJscreDataLength = 2;

 private:
  static String* last_ascii_string_;
  static String* two_byte_cached_string_;

  static int JscreNumberOfCaptures(Handle<JSRegExp> re);
  static ByteArray* JscreInternal(Handle<JSRegExp> re);

  static int IrregexpNumberOfCaptures(Handle<FixedArray> re);
  static int IrregexpNumberOfRegisters(Handle<FixedArray> re);
  static Handle<ByteArray> IrregexpByteCode(Handle<FixedArray> re);
  static Handle<Code> IrregexpNativeCode(Handle<FixedArray> re);

  // Call jsRegExpExecute once
  static Handle<Object> JscreExecOnce(Handle<JSRegExp> regexp,
                                      int num_captures,
                                      Handle<String> subject,
                                      int previous_index,
                                      const uc16* utf8_subject,
                                      int* ovector,
                                      int ovector_length);

  static Handle<Object> IrregexpExecOnce(Handle<FixedArray> regexp,
                                         int num_captures,
                                         Handle<String> subject16,
                                         int previous_index,
                                         int* ovector,
                                         int ovector_length);

  // Set the subject cache.  The previous string buffer is not deleted, so the
  // caller should ensure that it doesn't leak.
  static void SetSubjectCache(String* subject,
                              char* utf8_subject,
                              int uft8_length,
                              int character_position,
                              int utf8_position);

  // A one element cache of the last utf8_subject string and its length.  The
  // subject JS String object is cached in the heap.  We also cache a
  // translation between position and utf8 position.
  static char* utf8_subject_cache_;
  static int utf8_length_cache_;
  static int utf8_position_;
  static int character_position_;
};


class CharacterRange {
 public:
  CharacterRange() : from_(0), to_(0) { }
  // For compatibility with the CHECK_OK macro
  CharacterRange(void* null) { ASSERT_EQ(NULL, null); }  //NOLINT
  CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { }
  static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges);
  static Vector<const uc16> GetWordBounds();
  static inline CharacterRange Singleton(uc16 value) {
    return CharacterRange(value, value);
  }
  static inline CharacterRange Range(uc16 from, uc16 to) {
    ASSERT(from <= to);
    return CharacterRange(from, to);
  }
  static inline CharacterRange Everything() {
    return CharacterRange(0, 0xFFFF);
  }
  bool Contains(uc16 i) { return from_ <= i && i <= to_; }
  uc16 from() const { return from_; }
  void set_from(uc16 value) { from_ = value; }
  uc16 to() const { return to_; }
  void set_to(uc16 value) { to_ = value; }
  bool is_valid() { return from_ <= to_; }
  bool IsEverything(uc16 max) { return from_ == 0 && to_ >= max; }
  bool IsSingleton() { return (from_ == to_); }
  void AddCaseEquivalents(ZoneList<CharacterRange>* ranges);
  static void Split(ZoneList<CharacterRange>* base,
                    Vector<const uc16> overlay,
                    ZoneList<CharacterRange>** included,
                    ZoneList<CharacterRange>** excluded);

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

 private:
  uc16 from_;
  uc16 to_;
};


template <typename Node, class Callback>
static void DoForEach(Node* node, Callback* callback);


// A zone splay tree.  The config type parameter encapsulates the
// different configurations of a concrete splay tree:
//
//   typedef Key: the key type
//   typedef Value: the value type
//   static const kNoKey: the dummy key used when no key is set
//   static const kNoValue: the dummy value used to initialize nodes
//   int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function
//
template <typename Config>
class ZoneSplayTree : public ZoneObject {
 public:
  typedef typename Config::Key Key;
  typedef typename Config::Value Value;

  class Locator;

  ZoneSplayTree() : root_(NULL) { }

  // Inserts the given key in this tree with the given value.  Returns
  // true if a node was inserted, otherwise false.  If found the locator
  // is enabled and provides access to the mapping for the key.
  bool Insert(const Key& key, Locator* locator);

  // Looks up the key in this tree and returns true if it was found,
  // otherwise false.  If the node is found the locator is enabled and
  // provides access to the mapping for the key.
  bool Find(const Key& key, Locator* locator);

  // Finds the mapping with the greatest key less than or equal to the
  // given key.
  bool FindGreatestLessThan(const Key& key, Locator* locator);

  // Find the mapping with the greatest key in this tree.
  bool FindGreatest(Locator* locator);

  // Finds the mapping with the least key greater than or equal to the
  // given key.
  bool FindLeastGreaterThan(const Key& key, Locator* locator);

  // Find the mapping with the least key in this tree.
  bool FindLeast(Locator* locator);

  // Remove the node with the given key from the tree.
  bool Remove(const Key& key);

  bool is_empty() { return root_ == NULL; }

  // Perform the splay operation for the given key. Moves the node with
  // the given key to the top of the tree.  If no node has the given
  // key, the last node on the search path is moved to the top of the
  // tree.
  void Splay(const Key& key);

  class Node : public ZoneObject {
   public:
    Node(const Key& key, const Value& value)
        : key_(key),
          value_(value),
          left_(NULL),
          right_(NULL) { }
    Key key() { return key_; }
    Value value() { return value_; }
    Node* left() { return left_; }
    Node* right() { return right_; }
   private:
    friend class ZoneSplayTree;
    friend class Locator;
    Key key_;
    Value value_;
    Node* left_;
    Node* right_;
  };

  // A locator provides access to a node in the tree without actually
  // exposing the node.
  class Locator {
   public:
    explicit Locator(Node* node) : node_(node) { }
    Locator() : node_(NULL) { }
    const Key& key() { return node_->key_; }
    Value& value() { return node_->value_; }
    void set_value(const Value& value) { node_->value_ = value; }
    inline void bind(Node* node) { node_ = node; }
   private:
    Node* node_;
  };

  template <class Callback>
  void ForEach(Callback* c) {
    DoForEach<typename ZoneSplayTree<Config>::Node, Callback>(root_, c);
  }

 private:
  Node* root_;
};


// A set of unsigned integers that behaves especially well on small
// integers (< 32).  May do zone-allocation.
class OutSet: public ZoneObject {
 public:
  OutSet() : first_(0), remaining_(NULL), successors_(NULL) { }
  OutSet* Extend(unsigned value);
  bool Get(unsigned value);
  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);

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

  OutSet(uint32_t first, ZoneList<unsigned>* remaining)
      : first_(first), remaining_(remaining), successors_(NULL) { }
  uint32_t first_;
  ZoneList<unsigned>* remaining_;
  ZoneList<OutSet*>* successors_;
  friend class GenerationVariant;
};


// A mapping from integers, specified as ranges, to a set of integers.
// Used for mapping character ranges to choices.
class DispatchTable : public ZoneObject {
 public:
  class Entry {
   public:
    Entry() : from_(0), to_(0), out_set_(NULL) { }
    Entry(uc16 from, uc16 to, OutSet* out_set)
        : from_(from), to_(to), out_set_(out_set) { }
    uc16 from() { return from_; }
    uc16 to() { return to_; }
    void set_to(uc16 value) { to_ = value; }
    void AddValue(int value) { out_set_ = out_set_->Extend(value); }
    OutSet* out_set() { return out_set_; }
   private:
    uc16 from_;
    uc16 to_;
    OutSet* out_set_;
  };

  class Config {
   public:
    typedef uc16 Key;
    typedef Entry Value;
    static const uc16 kNoKey;
    static const Entry kNoValue;
    static inline int Compare(uc16 a, uc16 b) {
      if (a == b)
        return 0;
      else if (a < b)
        return -1;
      else
        return 1;
    }
  };

  void AddRange(CharacterRange range, int value);
  OutSet* Get(uc16 value);
  void Dump();

  template <typename Callback>
  void ForEach(Callback* callback) { return tree()->ForEach(callback); }
 private:
  // There can't be a static empty set since it allocates its
  // successors in a zone and caches them.
  OutSet* empty() { return &empty_; }
  OutSet empty_;
  ZoneSplayTree<Config>* tree() { return &tree_; }
  ZoneSplayTree<Config> tree_;
};


#define FOR_EACH_NODE_TYPE(VISIT)                                    \
  VISIT(End)                                                         \
  VISIT(Action)                                                      \
  VISIT(Choice)                                                      \
  VISIT(BackReference)                                               \
  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 Type {UNINITIALIZED, ATOM, CHAR_CLASS};
  TextElement() : type(UNINITIALIZED) { }
  explicit TextElement(Type t) : type(t), cp_offset(-1) { }
  static TextElement Atom(RegExpAtom* atom);
  static TextElement CharClass(RegExpCharacterClass* char_class);
  Type type;
  union {
    RegExpAtom* u_atom;
    RegExpCharacterClass* u_char_class;
  } data;
  int cp_offset;
};


class GenerationVariant;


struct NodeInfo {
  enum TriBool {
    UNKNOWN = -1, FALSE = 0, TRUE = 1
  };

  NodeInfo()
      : being_analyzed(false),
        been_analyzed(false),
        being_expanded(false),
        been_expanded(false),
        determine_word(false),
        determine_newline(false),
        determine_start(false),
        does_determine_word(false),
        does_determine_newline(false),
        does_determine_start(false),
        follows_word_interest(false),
        follows_newline_interest(false),
        follows_start_interest(false),
        is_word(UNKNOWN),
        is_newline(UNKNOWN),
        at_end(false),
        follows_word(UNKNOWN),
        follows_newline(UNKNOWN),
        follows_start(UNKNOWN),
        visited(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) &&
           (follows_word == that->follows_word) &&
           (follows_newline == that->follows_newline) &&
           (follows_start == that->follows_start) &&
           (does_determine_word == that->does_determine_word) &&
           (does_determine_newline == that->does_determine_newline) &&
           (does_determine_start == that->does_determine_start);
  }

  bool HasAssertions() {
    return (follows_word != UNKNOWN) ||
           (follows_newline != UNKNOWN) ||
           (follows_start != UNKNOWN);
  }

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

  void AddAssumptions(NodeInfo* that) {
    if (that->follows_word != UNKNOWN) {
      ASSERT(follows_word == UNKNOWN || follows_word == that->follows_word);
      follows_word = that->follows_word;
    }
    if (that->follows_newline != UNKNOWN) {
      ASSERT(follows_newline == UNKNOWN ||
             follows_newline == that->follows_newline);
      follows_newline = that->follows_newline;
    }
    if (that->follows_start != UNKNOWN) {
      ASSERT(follows_start == UNKNOWN ||
             follows_start == that->follows_start);
      follows_start = that->follows_start;
    }
    does_determine_word = that->does_determine_word;
    does_determine_newline = that->does_determine_newline;
    does_determine_start = that->does_determine_start;
  }

  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;
    being_expanded = false;
    been_expanded = false;
  }

  bool being_analyzed: 1;
  bool been_analyzed: 1;
  bool being_expanded: 1;
  bool been_expanded: 1;

  // These bits are set if this node must propagate forward information
  // about the last character it consumed (or, in the case of 'start',
  // if it is at the start of the input).
  bool determine_word: 1;
  bool determine_newline: 1;
  bool determine_start: 1;

  bool does_determine_word: 1;
  bool does_determine_newline: 1;
  bool does_determine_start: 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;

  TriBool is_word: 2;
  TriBool is_newline: 2;

  bool at_end: 1;

  // These bits are set if the node can make assumptions about what
  // the previous character was.
  TriBool follows_word: 2;
  TriBool follows_newline: 2;
  TriBool follows_start: 2;

  bool visited: 1;
};


class ExpansionGuard {
 public:
  explicit inline ExpansionGuard(NodeInfo* info) : info_(info) {
    ASSERT(!info->being_expanded);
    info->being_expanded = true;
  }
  inline ~ExpansionGuard() {
    info_->being_expanded = false;
  }
 private:
  NodeInfo* info_;
};


class SiblingList {
 public:
  SiblingList() : list_(NULL) { }
  int length() {
    return list_ == NULL ? 0 : list_->length();
  }
  void Ensure(RegExpNode* parent) {
    if (list_ == NULL) {
      list_ = new ZoneList<RegExpNode*>(2);
      list_->Add(parent);
    }
  }
  void Add(RegExpNode* node) { list_->Add(node); }
  RegExpNode* Get(int index) { return list_->at(index); }
 private:
  ZoneList<RegExpNode*>* list_;
};


class RegExpNode: public ZoneObject {
 public:
  RegExpNode() : variants_generated_(0) { }
  virtual ~RegExpNode() { }
  virtual void Accept(NodeVisitor* visitor) = 0;
  // Generates a goto to this node or actually generates the code at this point.
  // Until the implementation is complete we will return true for success and
  // false for failure.
  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant) = 0;
  static const int kNodeIsTooComplexForGreedyLoops = -1;
  virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
  Label* label() { return &label_; }
  static const int kMaxVariantsGenerated = 10;

  RegExpNode* EnsureExpanded(NodeInfo* info);
  virtual RegExpNode* ExpandLocal(NodeInfo* info) = 0;
  virtual void ExpandChildren() = 0;

  // Propagates the given interest information forward.  When seeing
  // \bfoo for instance, the \b is implemented by propagating forward
  // to the 'foo' string that it should only succeed if its first
  // character is a letter xor the previous character was a letter.
  virtual RegExpNode* PropagateForward(NodeInfo* info) = 0;

  NodeInfo* info() { return &info_; }

  void AddSibling(RegExpNode* node) { siblings_.Add(node); }

  // Static version of EnsureSibling that expresses the fact that the
  // result has the same type as the input.
  template <class C>
  static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) {
    return static_cast<C*>(node->EnsureSibling(info, cloned));
  }

  SiblingList* siblings() { return &siblings_; }
  void set_siblings(SiblingList* other) { siblings_ = *other; }

 protected:
  enum LimitResult { DONE, FAIL, CONTINUE };
  LimitResult LimitVersions(RegExpCompiler* compiler,
                            GenerationVariant* variant);

  // Returns a sibling of this node whose interests and assumptions
  // match the ones in the given node info.  If no sibling exists NULL
  // is returned.
  RegExpNode* TryGetSibling(NodeInfo* info);

  // Returns a sibling of this node whose interests match the ones in
  // the given node info.  The info must not contain any assertions.
  // If no node exists a new one will be created by cloning the current
  // node.  The result will always be an instance of the same concrete
  // class as this node.
  RegExpNode* EnsureSibling(NodeInfo* info, bool* cloned);

  // Returns a clone of this node initialized using the copy constructor
  // of its concrete class.  Note that the node may have to be pre-
  // processed before it is on a useable state.
  virtual RegExpNode* Clone() = 0;

 private:
  Label label_;
  NodeInfo info_;
  SiblingList siblings_;
  int variants_generated_;
};


class SeqRegExpNode: public RegExpNode {
 public:
  explicit SeqRegExpNode(RegExpNode* on_success)
      : on_success_(on_success) { }
  RegExpNode* on_success() { return on_success_; }
  void set_on_success(RegExpNode* node) { on_success_ = node; }
 private:
  RegExpNode* on_success_;
};


class ActionNode: public SeqRegExpNode {
 public:
  enum Type {
    SET_REGISTER,
    INCREMENT_REGISTER,
    STORE_POSITION,
    BEGIN_SUBMATCH,
    POSITIVE_SUBMATCH_SUCCESS
  };
  static ActionNode* SetRegister(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* BeginSubmatch(
      int stack_pointer_reg,
      int position_reg,
      RegExpNode* on_success);
  static ActionNode* PositiveSubmatchSuccess(
      int stack_pointer_reg,
      int restore_reg,
      RegExpNode* on_success);
  virtual void Accept(NodeVisitor* visitor);
  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
  virtual RegExpNode* ExpandLocal(NodeInfo* info);
  virtual void ExpandChildren();
  virtual RegExpNode* PropagateForward(NodeInfo* info);
  Type type() { return type_; }
  // TODO(erikcorry): We should allow some action nodes in greedy loops.
  virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
  virtual ActionNode* Clone() { return new ActionNode(*this); }

 private:
  union {
    struct {
      int reg;
      int value;
    } u_store_register;
    struct {
      int reg;
    } u_increment_register;
    struct {
      int reg;
    } u_position_register;
    struct {
      int stack_pointer_register;
      int current_position_register;
    } u_submatch;
  } data_;
  ActionNode(Type type, RegExpNode* on_success)
      : SeqRegExpNode(on_success),
        type_(type) { }
  Type type_;
  friend class DotPrinter;
};


class TextNode: public SeqRegExpNode {
 public:
  TextNode(ZoneList<TextElement>* elms,
           RegExpNode* on_success)
      : SeqRegExpNode(on_success),
        elms_(elms) { }
  TextNode(RegExpCharacterClass* that,
           RegExpNode* on_success)
      : SeqRegExpNode(on_success),
        elms_(new ZoneList<TextElement>(1)) {
    elms_->Add(TextElement::CharClass(that));
  }
  virtual void Accept(NodeVisitor* visitor);
  virtual RegExpNode* PropagateForward(NodeInfo* info);
  virtual RegExpNode* ExpandLocal(NodeInfo* info);
  virtual void ExpandChildren();
  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
  ZoneList<TextElement>* elements() { return elms_; }
  void MakeCaseIndependent();
  virtual int GreedyLoopTextLength();
  virtual TextNode* Clone() {
    TextNode* result = new TextNode(*this);
    result->CalculateOffsets();
    return result;
  }
  void CalculateOffsets();
 private:
  void ExpandAtomChildren(RegExpAtom* that);
  void ExpandCharClassChildren(RegExpCharacterClass* that);

  ZoneList<TextElement>* elms_;
};


class BackReferenceNode: public SeqRegExpNode {
 public:
  BackReferenceNode(int start_reg,
                    int end_reg,
                    RegExpNode* on_success)
      : SeqRegExpNode(on_success),
        start_reg_(start_reg),
        end_reg_(end_reg) { }
  virtual void Accept(NodeVisitor* visitor);
  int start_register() { return start_reg_; }
  int end_register() { return end_reg_; }
  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
  virtual RegExpNode* PropagateForward(NodeInfo* info);
  virtual RegExpNode* ExpandLocal(NodeInfo* info);
  virtual void ExpandChildren();
  virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }

 private:
  int start_reg_;
  int end_reg_;
};


class EndNode: public RegExpNode {
 public:
  enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
  explicit EndNode(Action action) : action_(action) { }
  virtual void Accept(NodeVisitor* visitor);
  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
  virtual RegExpNode* PropagateForward(NodeInfo* info);
  virtual RegExpNode* ExpandLocal(NodeInfo* info);
  virtual void ExpandChildren();
  virtual EndNode* Clone() { return new EndNode(*this); }

 protected:
  void EmitInfoChecks(RegExpMacroAssembler* macro, GenerationVariant* variant);

 private:
  Action action_;
};


class NegativeSubmatchSuccess: public EndNode {
 public:
  NegativeSubmatchSuccess(int stack_pointer_reg, int position_reg)
      : EndNode(NEGATIVE_SUBMATCH_SUCCESS),
        stack_pointer_register_(stack_pointer_reg),
        current_position_register_(position_reg) { }
  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);

 private:
  int stack_pointer_register_;
  int current_position_register_;
};


class Guard: public ZoneObject {
 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_;
};


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

 private:
  RegExpNode* node_;
  ZoneList<Guard*>* guards_;
};


class ChoiceNode: public RegExpNode {
 public:
  explicit ChoiceNode(int expected_size)
      : alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
        table_(NULL),
        being_calculated_(false) { }
  virtual void Accept(NodeVisitor* visitor);
  void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
  ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
  DispatchTable* GetTable(bool ignore_case);
  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
  virtual RegExpNode* PropagateForward(NodeInfo* info);
  virtual RegExpNode* ExpandLocal(NodeInfo* info);
  virtual void ExpandChildren();
  virtual ChoiceNode* Clone() { return new ChoiceNode(*this); }

  bool being_calculated() { return being_calculated_; }
  void set_being_calculated(bool b) { being_calculated_ = b; }

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

 private:
  friend class DispatchTableConstructor;
  friend class AssertionPropagation;
  void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                     Guard *guard,
                     GenerationVariant* variant);
  DispatchTable* table_;
  bool being_calculated_;
};


class LoopChoiceNode: public ChoiceNode {
 public:
  explicit LoopChoiceNode(int expected_size) : ChoiceNode(expected_size) { }
  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
  virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); }
};


// 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.
class GenerationVariant {
 public:
  class DeferredAction {
   public:
    DeferredAction(ActionNode::Type type, int reg)
        : type_(type), reg_(reg), next_(NULL) { }
    DeferredAction* next() { return next_; }
    int reg() { return reg_; }
    ActionNode::Type type() { return type_; }
   private:
    ActionNode::Type type_;
    int reg_;
    DeferredAction* next_;
    friend class GenerationVariant;
  };

  class DeferredCapture: public DeferredAction {
   public:
    DeferredCapture(int reg, GenerationVariant* variant)
        : DeferredAction(ActionNode::STORE_POSITION, reg),
          cp_offset_(variant->cp_offset()) { }
    int cp_offset() { return cp_offset_; }
   private:
    int cp_offset_;
    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 DeferredIncrementRegister: public DeferredAction {
   public:
    explicit DeferredIncrementRegister(int reg)
        : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { }
  };

  explicit GenerationVariant(Label* backtrack)
      : cp_offset_(0),
        actions_(NULL),
        backtrack_(backtrack),
        stop_node_(NULL),
        loop_label_(NULL) { }
  GenerationVariant()
      : cp_offset_(0),
        actions_(NULL),
        backtrack_(NULL),
        stop_node_(NULL),
        loop_label_(NULL) { }
  bool Flush(RegExpCompiler* compiler, RegExpNode* successor);
  int cp_offset() { return cp_offset_; }
  DeferredAction* actions() { return actions_; }
  bool is_trivial() {
    return backtrack_ == NULL && actions_ == NULL && cp_offset_ == 0;
  }
  Label* backtrack() { return backtrack_; }
  Label* loop_label() { return loop_label_; }
  RegExpNode* stop_node() { return stop_node_; }
  // These set methods should be used only on new GenerationVariants - the
  // intention is that GenerationVariants are immutable after creation.
  void add_action(DeferredAction* new_action) {
    ASSERT(new_action->next_ == NULL);
    new_action->next_ = actions_;
    actions_ = new_action;
  }
  void set_cp_offset(int new_cp_offset) {
    ASSERT(new_cp_offset >= cp_offset_);
    cp_offset_ = new_cp_offset;
  }
  void set_backtrack(Label* backtrack) { backtrack_ = backtrack; }
  void set_stop_node(RegExpNode* node) { stop_node_ = node; }
  void set_loop_label(Label* label) { loop_label_ = label; }
  bool mentions_reg(int reg);
 private:
  int FindAffectedRegisters(OutSet* affected_registers);
  void PerformDeferredActions(RegExpMacroAssembler* macro,
                               int max_register,
                               OutSet& affected_registers);
  void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
                                int max_register,
                                OutSet& affected_registers);
  void PushAffectedRegisters(RegExpMacroAssembler* macro,
                             int max_register,
                             OutSet& affected_registers);
  int cp_offset_;
  DeferredAction* actions_;
  Label* backtrack_;
  RegExpNode* stop_node_;
  Label* loop_label_;
};
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
};


// Node visitor used to add the start set of the alternatives to the
// dispatch table of a choice node.
class DispatchTableConstructor: public NodeVisitor {
 public:
  DispatchTableConstructor(DispatchTable* table, bool ignore_case)
      : table_(table),
        choice_index_(-1),
        ignore_case_(ignore_case) { }

  void BuildTable(ChoiceNode* node);

  void AddRange(CharacterRange range) {
    table()->AddRange(range, choice_index_);
  }

  void AddInverse(ZoneList<CharacterRange>* ranges);

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

  DispatchTable* table() { return table_; }
  void set_choice_index(int value) { choice_index_ = value; }

 protected:
  DispatchTable *table_;
  int choice_index_;
  bool ignore_case_;
};


// 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 |
//   +-------+        +------------+
//
// At a later phase all nodes that determine information for their
// following nodes are split into several 'sibling' nodes.  In this
// case the first '.' is split into one node that only matches words
// and one that only matches non-words.  The second '.' is also split,
// into one node that assumes that the previous character was a word
// character and one that assumes that is was non-word.  In this case
// the result is
//
//         +------------------+        +------------------+
//   /-->  | intersect(., \w) |  --->  | intersect(., \W) |
//   |     +------------------+        +------------------+
//   |                                 |    follows \w    |
//   |                                 +------------------+
// --?
//   |     +------------------+        +------------------+
//   \-->  | intersect(., \W) |  --->  | intersect(., \w) |
//         +------------------+        +------------------+
//                                     |    follows \W    |
//                                     +------------------+
//
// This way we don't need to explicitly check the previous character
// but can always assume that whoever consumed the previous character
// has propagated the relevant information forward.
class AssertionPropagation: public NodeVisitor {
 public:
  explicit AssertionPropagation(bool ignore_case)
      : ignore_case_(ignore_case) { }
  void EnsureAnalyzed(RegExpNode* node);

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

 private:
  bool ignore_case_;

  DISALLOW_IMPLICIT_CONSTRUCTORS(AssertionPropagation);
};


struct RegExpCompileData {
  RegExpCompileData()
    : tree(NULL),
      node(NULL),
      has_lookbehind(false),
      has_character_escapes(false),
      capture_count(0) { }
  RegExpTree* tree;
  RegExpNode* node;
  bool has_lookbehind;
  bool has_character_escapes;
  Handle<String> error;
  int capture_count;
};


class RegExpEngine: public AllStatic {
 public:
  static Handle<FixedArray> Compile(RegExpCompileData* input,
                                    bool ignore_case,
                                    bool multiline,
                                    Handle<String> pattern,
                                    bool is_ascii);

  static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
};


} }  // namespace v8::internal

#endif  // V8_JSREGEXP_H_