text: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   * vim: set ts=8 sts=4 et sw=4 tw=99: */
  
  // 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_REGEXP_AST_H_
  #define V8_REGEXP_AST_H_
  
  // Prevent msvc build failures as indicated in bug 1205328
  #ifdef min
  # undef min
  #endif
  #ifdef max
  # undef max
  #endif
  
  #include "irregexp/RegExpEngine.h"
  
  namespace js {
  namespace irregexp {
  
  class RegExpCompiler;
  class RegExpNode;
  
  class RegExpVisitor
  {
    public:
      virtual ~RegExpVisitor() { }
  #define MAKE_CASE(Name)                                         \
      virtual void* Visit##Name(RegExp##Name*, void* data) = 0;
      FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
  #undef MAKE_CASE
  };
  
  class RegExpTree
  {
    public:
      static const int kInfinity = INT32_MAX;
      virtual ~RegExpTree() {}
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success) = 0;
      virtual bool IsTextElement() { return false; }
      virtual bool IsAnchoredAtStart() { return false; }
      virtual bool IsAnchoredAtEnd() { return false; }
      virtual int min_match() = 0;
      virtual int max_match() = 0;
      // Returns the interval of registers used for captures within this
      // expression.
      virtual Interval CaptureRegisters() { return Interval::Empty(); }
      virtual void AppendToText(RegExpText* text) {
          MOZ_CRASH("Bad call");
      }
  #define MAKE_ASTYPE(Name)                                               \
      virtual RegExp##Name* As##Name();                                   \
      virtual bool Is##Name();
      FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE)
  #undef MAKE_ASTYPE
  };
  
  typedef Vector<RegExpTree*, 1, LifoAllocPolicy<Infallible> > RegExpTreeVector;
  
  class RegExpDisjunction : public RegExpTree
  {
    public:
      explicit RegExpDisjunction(RegExpTreeVector* alternatives);
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      virtual RegExpDisjunction* AsDisjunction();
      virtual Interval CaptureRegisters();
      virtual bool IsDisjunction();
      virtual bool IsAnchoredAtStart();
      virtual bool IsAnchoredAtEnd();
      virtual int min_match() { return min_match_; }
      virtual int max_match() { return max_match_; }
  
      const RegExpTreeVector& alternatives() { return *alternatives_; }
  
    private:
      RegExpTreeVector* alternatives_;
      int min_match_;
      int max_match_;
  };
  
  class RegExpAlternative : public RegExpTree
  {
    public:
      explicit RegExpAlternative(RegExpTreeVector* nodes);
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      virtual RegExpAlternative* AsAlternative();
      virtual Interval CaptureRegisters();
      virtual bool IsAlternative();
      virtual bool IsAnchoredAtStart();
      virtual bool IsAnchoredAtEnd();
      virtual int min_match() { return min_match_; }
      virtual int max_match() { return max_match_; }
  
      const RegExpTreeVector& nodes() { return *nodes_; }
  
    private:
      RegExpTreeVector* nodes_;
      int min_match_;
      int max_match_;
  };
  
  class RegExpAssertion : public RegExpTree {
   public:
    enum AssertionType {
      START_OF_LINE,
      START_OF_INPUT,
      END_OF_LINE,
      END_OF_INPUT,
      BOUNDARY,
      NON_BOUNDARY
    };
    explicit RegExpAssertion(AssertionType type) : assertion_type_(type) { }
    virtual void* Accept(RegExpVisitor* visitor, void* data);
    virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                               RegExpNode* on_success);
    virtual RegExpAssertion* AsAssertion();
    virtual bool IsAssertion();
    virtual bool IsAnchoredAtStart();
    virtual bool IsAnchoredAtEnd();
    virtual int min_match() { return 0; }
    virtual int max_match() { return 0; }
    AssertionType assertion_type() { return assertion_type_; }
   private:
    AssertionType assertion_type_;
  };
  
  class CharacterSet
  {
    public:
      explicit CharacterSet(char16_t standard_set_type)
        : ranges_(nullptr),
          standard_set_type_(standard_set_type)
      {}
      explicit CharacterSet(CharacterRangeVector* ranges)
        : ranges_(ranges),
          standard_set_type_(0)
      {}
  
      CharacterRangeVector& ranges(LifoAlloc* alloc);
      char16_t standard_set_type() { return standard_set_type_; }
      void set_standard_set_type(char16_t special_set_type) {
          standard_set_type_ = special_set_type;
      }
      bool is_standard() { return standard_set_type_ != 0; }
      void Canonicalize();
  
    private:
      CharacterRangeVector* ranges_;
  
      // If non-zero, the value represents a standard set (e.g., all whitespace
      // characters) without having to expand the ranges.
      char16_t standard_set_type_;
  };
  
  class RegExpCharacterClass : public RegExpTree
  {
    public:
      RegExpCharacterClass(CharacterRangeVector* ranges, bool is_negated)
        : set_(ranges),
          is_negated_(is_negated)
      {}
  
      explicit RegExpCharacterClass(char16_t type)
        : set_(type),
          is_negated_(false)
      {}
  
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      virtual RegExpCharacterClass* AsCharacterClass();
      virtual bool IsCharacterClass();
      virtual bool IsTextElement() { return true; }
      virtual int min_match() { return 1; }
      virtual int max_match() { return 1; }
      virtual void AppendToText(RegExpText* text);
  
      CharacterSet character_set() { return set_; }
  
      // TODO(lrn): Remove need for complex version if is_standard that
      // recognizes a mangled standard set and just do { return set_.is_special(); }
      bool is_standard(LifoAlloc* alloc);
  
      // Returns a value representing the standard character set if is_standard()
      // returns true.
      // Currently used values are:
      // s : unicode whitespace
      // S : unicode non-whitespace
      // w : ASCII word character (digit, letter, underscore)
      // W : non-ASCII word character
      // d : ASCII digit
      // D : non-ASCII digit
      // . : non-unicode non-newline
      // * : All characters
      char16_t standard_type() { return set_.standard_set_type(); }
  
      CharacterRangeVector& ranges(LifoAlloc* alloc) { return set_.ranges(alloc); }
      bool is_negated() { return is_negated_; }
  
    private:
      CharacterSet set_;
      bool is_negated_;
  };
  
  typedef Vector<char16_t, 10, LifoAllocPolicy<Infallible> > CharacterVector;
  
  class RegExpAtom : public RegExpTree
  {
    public:
      explicit RegExpAtom(CharacterVector* data)
        : data_(data)
      {}
  
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      virtual RegExpAtom* AsAtom();
      virtual bool IsAtom();
      virtual bool IsTextElement() { return true; }
      virtual int min_match() { return data_->length(); }
      virtual int max_match() { return data_->length(); }
      virtual void AppendToText(RegExpText* text);
  
      const CharacterVector& data() { return *data_; }
      int length() { return data_->length(); }
  
    private:
      CharacterVector* data_;
  };
  
  class RegExpText : public RegExpTree
  {
    public:
      explicit RegExpText(LifoAlloc* alloc)
        : elements_(*alloc), length_(0)
      {}
  
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      virtual RegExpText* AsText();
      virtual bool IsText();
      virtual bool IsTextElement() { return true; }
      virtual int min_match() { return length_; }
      virtual int max_match() { return length_; }
      virtual void AppendToText(RegExpText* text);
  
      void AddElement(TextElement elm)  {
          elements_.append(elm);
          length_ += elm.length();
      }
      const TextElementVector& elements() { return elements_; }
  
    private:
      TextElementVector elements_;
      int length_;
  };
  
  class RegExpQuantifier : public RegExpTree
  {
    public:
      enum QuantifierType { GREEDY, NON_GREEDY, POSSESSIVE };
      RegExpQuantifier(int min, int max, QuantifierType type, RegExpTree* body)
        : body_(body),
          min_(min),
          max_(max),
          min_match_(min * body->min_match()),
          quantifier_type_(type)
      {
          if (max > 0 && body->max_match() > kInfinity / max) {
              max_match_ = kInfinity;
          } else {
              max_match_ = max * body->max_match();
          }
      }
  
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      static RegExpNode* ToNode(int min,
                                int max,
                                bool is_greedy,
                                RegExpTree* body,
                                RegExpCompiler* compiler,
                                RegExpNode* on_success,
                                bool not_at_start = false);
      virtual RegExpQuantifier* AsQuantifier();
      virtual Interval CaptureRegisters();
      virtual bool IsQuantifier();
      virtual int min_match() { return min_match_; }
      virtual int max_match() { return max_match_; }
      int min() { return min_; }
      int max() { return max_; }
      bool is_possessive() { return quantifier_type_ == POSSESSIVE; }
      bool is_non_greedy() { return quantifier_type_ == NON_GREEDY; }
      bool is_greedy() { return quantifier_type_ == GREEDY; }
      RegExpTree* body() { return body_; }
  
    private:
      RegExpTree* body_;
      int min_;
      int max_;
      int min_match_;
      int max_match_;
      QuantifierType quantifier_type_;
  };
  
  class RegExpCapture : public RegExpTree
  {
    public:
      explicit RegExpCapture(RegExpTree* body, int index)
        : body_(body), index_(index)
      {}
  
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      static RegExpNode* ToNode(RegExpTree* body,
                                int index,
                                RegExpCompiler* compiler,
                                RegExpNode* on_success);
      virtual RegExpCapture* AsCapture();
      virtual bool IsAnchoredAtStart();
      virtual bool IsAnchoredAtEnd();
      virtual Interval CaptureRegisters();
      virtual bool IsCapture();
      virtual int min_match() { return body_->min_match(); }
      virtual int max_match() { return body_->max_match(); }
      RegExpTree* body() { return body_; }
      int index() { return index_; }
      static int StartRegister(int index) { return index * 2; }
      static int EndRegister(int index) { return index * 2 + 1; }
  
    private:
      RegExpTree* body_;
      int index_;
  };
  
  class RegExpLookahead : public RegExpTree
  {
    public:
      RegExpLookahead(RegExpTree* body,
                      bool is_positive,
                      int capture_count,
                      int capture_from)
        : body_(body),
          is_positive_(is_positive),
          capture_count_(capture_count),
          capture_from_(capture_from)
      {}
  
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      virtual RegExpLookahead* AsLookahead();
      virtual Interval CaptureRegisters();
      virtual bool IsLookahead();
      virtual bool IsAnchoredAtStart();
      virtual int min_match() { return 0; }
      virtual int max_match() { return 0; }
      RegExpTree* body() { return body_; }
      bool is_positive() { return is_positive_; }
      int capture_count() { return capture_count_; }
      int capture_from() { return capture_from_; }
  
    private:
      RegExpTree* body_;
      bool is_positive_;
      int capture_count_;
      int capture_from_;
  };
  
  typedef Vector<RegExpCapture*, 1, LifoAllocPolicy<Infallible> > RegExpCaptureVector;
  
  class RegExpBackReference : public RegExpTree
  {
    public:
      explicit RegExpBackReference(RegExpCapture* capture)
        : capture_(capture)
      {}
  
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      virtual RegExpBackReference* AsBackReference();
      virtual bool IsBackReference();
      virtual int min_match() { return 0; }
      virtual int max_match() { return capture_->max_match(); }
      int index() { return capture_->index(); }
      RegExpCapture* capture() { return capture_; }
    private:
      RegExpCapture* capture_;
  };
  
  class RegExpEmpty : public RegExpTree
  {
    public:
      RegExpEmpty()
      {}
  
      virtual void* Accept(RegExpVisitor* visitor, void* data);
      virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success);
      virtual RegExpEmpty* AsEmpty();
      virtual bool IsEmpty();
      virtual int min_match() { return 0; }
      virtual int max_match() { return 0; }
      static RegExpEmpty* GetInstance() {
          static RegExpEmpty instance;
          return &instance;
      }
  };
  
  } } // namespace js::irregexp
  
  #endif  // V8_REGEXP_AST_H_
  